최단경로. [9370]

[1. 문제 설명]

임의의 출발지에서 임의의 목적지들에 최단 경로로 갈 때,

특정 경로를 거치는 경로 역시 각 목적지들에 대해 최단 경로가 될 수 있는가?

 

 

[2. 풀이 접근]

A. 오답이었던 접근 방법 1

1. 다익스트라 탐색 중, 특정 경로를 통과한 정보를 추가로 저장함
   (from -> to 가 문제에 제시된 각 노드라면 true, 그렇지 않다면 false)
2. 다익스트라 탐색 중, 목적지 노드에 도착한 경우, from node 내 정보를 토대로,
   특정 경로를 통과했다면, 해당 목적지는 특정 경로를 통과했다고 저장.
   (경로 코스트의 합이 최소랑 같다면 => 최단 경로가 여러개 있는 것으로, true 일때 만 저장(default: false),
    경로 코스트의 합이 최소라면 => true, false 상관 없이 저장)
3. 다익스트라 종료 후 각 목적지에 대해 T/F 확인 후, 출력 여부 결정

=> 이 때 풀었던 방법과 비슷한 접근(?) ## https://testkernelv2.tistory.com/344

 

 

B. 오답이었던 접근 방법 2

1. parents 배열을 토대로 목적지 노드에서 출발지 노드로 거슬러 올라가면서 최단 경로를 복원
2. 이 때, 특정 노드를 방문하였는지 체크
3. 모두 방문하였으면 출력 / 그렇지 않으면 출력하지 않는다.
   => 이 접근이 틀린 이유는, 임의의 정점 둘이 연속되지 않을 수 있기 때문이다.
   => g ->h 방문이 아니고, g -> a1 -> b1 ->h  이렇게 방문했을 수도 있기 때문

 

C. 올바른 접근 방법

1. 경유지 문제로 바라보는 것

=> 비슷한 풀이를 갖는 문제 =>  https://testkernelv2.tistory.com/344

 

위 문제랑 비슷한 실수를 반복하였음.

 

priority queue 를 사용하는 다익스트라 알고리즘의 시간복잡도는 

O(ElogV) 로 문제 입력 상 최대로 대략 O(2000*16) 이므로 그렇게 시간을 많이 차지 하지 않는다.

 

다익스트라를 여러번 호출해도 큰 무리가 없다.

 

 

[3. 코드]

 

 

[4. 코드 - fail]