정해는 테이블에 first hop 자체를 갱신하는 것이고, 제 코드가 불필요한 탐색을 한다는 것은 인지하고 있습니다! 다만 적용하기 전에 생각한 방식을 검토해보고 싶어 질문 드립니다.
1719번 - 택배
정해는 테이블에 first hop 자체를 갱신하는 것이고, 제 코드가 불필요한 탐색을 한다는 것은 인지하고 있습니다! 다만 적용하기 전에 생각한 방식을 검토해보고 싶어 질문 드립니다.
아래와 같이 바꾸고 p 배열을 그대로 출력하면 제 풀이와 같아지는데, "first hop 자체를 갱신"한다고 하신 걸 보아 두 풀이가 동등하다는 걸 이미 파악하신 것 같습니다.
제 방식은
경로 파이프라인을 길이 1까지 축소하는 느낌이고
제시해주신 풀이는
길이1 경로를 파이프라인에 모두 덮어 씌운다는 느낌으로 여겼습니다.
과정은 다르고 결과는 같다..가 맞을까요
p[i][j] = k; 이렇게 쓰면 p 배열은 바로 다음 1스텝씩만 저장해서 출력할 때 while loop을 돌려서 따라가는 방식이 되고
p[i][j] = p[i][k]; 이렇게 쓰면 p 배열을 채울 때 이미 합치면서 채우기 때문에 그대로 출력하면 됩니다. p 배열 안에서 간단한 DP가 진행된다고도 볼 수 있지요.
출력 부분과 그 전 부분 사이의 작업량 분담이 달라질 뿐 코드 전체로 보면 데이터가 다뤄지는 과정은 완전히 일치한다고 주장하고 싶네요.
이해했습니다. 이렇게 보니 같아지는 이유를 알 것 같아요 감사드립니다!
댓글을 작성하려면 로그인해야 합니다.
dltkdgkr123 11달 전
문제 tc 개수가 적은 것 같아서 풀었음에도 확신을 못하겠습니다.
해당 문제는 모든 정점 to 모든 정점을 최단 거리로 이동할 때,
출발 지점에서 가장 먼저 이동해야 하는 정점(first hop)을 출력하는 것입니다. (가중치는 1 이상이고, 문제 조건에는 없지만 모든 정점은 이어져 있습니다.)
제 코드는
k1 = s -> e의 중간 지점
k2 = s -> k1의 중간 지점
..
kn = s -> kn-1의 중간 지점
이런식으로, 최단경로의 중간지점의 중간지점의 중간지점...을 찾는 방법입니다.
이러다보면 결국, 중간지점이 시작지점이 될때까지 축소되고, 이때 종단지점이 시작지점에 바로 인접한 부분(first hop)이 된다는 생각입니다.
중간지점이 최단경로 내 어느곳으로 주어지던(벨만-포드 탐색 순서에 따라 무작위로 바뀌어도) 적용 가능하다고 생각했습니다.
이 방식이 올바름을 보장하나요?