최단 경로. [1504]

[1. 문제 설명]

임의로 주어진 두 정점을 반드시 통과하면서

1번 정점에서 N번 정점으로 최단거리를 구한다.

(이 과정에서 한번 이동했던 정점은 물론 간선도 다시 이동 할 수 있다.)

 

 

[2. 풀이 접근]

A. 오답이었던 접근 방식

1. 현재 반드시 지나야 하는 정점의 개수를 기록하여
   int costs[2][N]; 을 업데이트 함
   => 비슷한 문제가 있었음. (https://testkernelv2.tistory.com/337)
   
   
2. 반드시 지나야 하는 정점의 개수를 셀 때,
   같은 정점을 두번지나는 경우를 방지하기 위한 처리 
   => 현재 인접 정점을 테스트 할 때, heap 에서 pop 한 노드에 저장된 slice 를 순회하여
   같은 정점인지 아닌지를 체크 후, 업데이트

 

한번에 다익스트라 실행으로 답을 구할 수 있을 것으로 생각했었다.

위 방법이 오답인 이유는 정확한 이유는 모르겠지만,

다익스트라는 충분히 빠르다고 볼 수 있으므로, 여러번 수행해도 시간에 큰 영향을 끼치지 않는다.(?)

 

 

B. 올바른 접근 방식

굉장히 단순한 접근

 

Source -> v1 -> v2 -> target

Source -> v2 -> v1 -> target 

 

의 최단 거리를 비교 후, 적절한 값을 출력한다.

경유지를 거쳐 이동하는 방식으로, 가장 확실한 방법이라 볼 수 있다.

 

 

[3. 코드]

 

 

 

[4 틀린 코드]