dltkdgkr123   11달 전

문제 tc 개수가 적은 것 같아서 풀었음에도 확신을 못하겠습니다.

해당 문제는 모든 정점 to 모든 정점을 최단 거리로 이동할 때,

출발 지점에서 가장 먼저 이동해야 하는 정점(first hop)을 출력하는 것입니다. (가중치는 1 이상이고, 문제 조건에는 없지만 모든 정점은 이어져 있습니다.)

제 코드는


k1 = s -> e의 중간 지점

k2 = s -> k1의 중간 지점

..

kn = s -> kn-1의 중간 지점

이런식으로, 최단경로의 중간지점의 중간지점의 중간지점...을 찾는 방법입니다.

이러다보면 결국, 중간지점이 시작지점이 될때까지 축소되고, 이때 종단지점이 시작지점에 바로 인접한 부분(first hop)이 된다는 생각입니다.

중간지점이 최단경로 내 어느곳으로 주어지던(벨만-포드 탐색 순서에 따라 무작위로 바뀌어도) 적용 가능하다고 생각했습니다.

이 방식이 올바름을 보장하나요?

dltkdgkr123   11달 전

정해는 테이블에 first hop 자체를 갱신하는 것이고, 제 코드가 불필요한 탐색을 한다는 것은 인지하고 있습니다! 다만 적용하기 전에 생각한 방식을 검토해보고 싶어 질문 드립니다.

zenith82114   11달 전

아래와 같이 바꾸고 p 배열을 그대로 출력하면 제 풀이와 같아지는데, "first hop 자체를 갱신"한다고 하신 걸 보아 두 풀이가 동등하다는 걸 이미 파악하신 것 같습니다.

dltkdgkr123   11달 전

제 방식은

경로 파이프라인을 길이 1까지 축소하는 느낌이고

제시해주신 풀이는

길이1 경로를 파이프라인에 모두 덮어 씌운다는 느낌으로 여겼습니다.


과정은 다르고 결과는 같다..가 맞을까요

zenith82114   11달 전

p[i][j] = k; 이렇게 쓰면 p 배열은 바로 다음 1스텝씩만 저장해서 출력할 때 while loop을 돌려서 따라가는 방식이 되고

p[i][j] = p[i][k]; 이렇게 쓰면 p 배열을 채울 때 이미 합치면서 채우기 때문에 그대로 출력하면 됩니다. p 배열 안에서 간단한 DP가 진행된다고도 볼 수 있지요.

출력 부분과 그 전 부분 사이의 작업량 분담이 달라질 뿐 코드 전체로 보면 데이터가 다뤄지는 과정은 완전히 일치한다고 주장하고 싶네요.

dltkdgkr123   11달 전

이해했습니다. 이렇게 보니 같아지는 이유를 알 것 같아요 감사드립니다!

댓글을 작성하려면 로그인해야 합니다.