[백준 9370 C++] 미확인 도착지

오늘은 백준(BOJ) 9370번 미확인 도착지 문제에 대해 다뤄볼 예정이다.

미확인 도착지 문제 링크 (백준(BOJ) 9370번 문제): https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

 

문제 설명 

백준 9370번 미확인 도착지 문제는 시작 위치에서 목적지 까지 최단거리로 갔을 때, 특정 경로(h->g 혹은 g->h)를 거쳐서 간 경우에 목적지를 출력하는 문제이다. 

미확인 도착지 예제

위 그래프를 예시로 들자면, 시작 위치(2)에서 도착 위치(5, 6)에 최단 거리로 갈 때, 특정 경로(1과3 사이의 Path [h->g 혹은 g->h])를 거친 후 도착한 경우 목적지를 출력 해준다. 

 

문제 풀이 

백준 9370번 미확인 도착지 문제의 핵심은 S -> G -> H -> D 혹은 S -> H -> G -> D 의 경로로 최단 거리를 구해주는 것이다. 

다음으로, 다익스트라 알고리즘 코드 구현이 중요하다고 볼 수 있다. 그 이유는 다익스트라 알고리즘 코드 때문에 해당 문제에서 66%에서 계속 시간 초과를 냈었기 때문이다....

 

66%에서 시간 초과를 나게 했었던 코드는 우선 순위 큐 때문이었다. 

문제의 코드: priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> pq ; 

우선 순위 큐를 선언할 때, 음수 값으로 접근하지 않고 우선 순위 큐 안에서 pair에 첫 번째 요소를 기준으로 낮은 Weight 이 앞에 오도록 해주는 greater<pair<int,int>> 를 사용했었다. 

이 코드를 사용하게 되니, 노드 수가 엄청 많아졌을 때, 시간 초과가 발생하게 되었던 것 이었다. 

 

실제로 clock_t를 통해 테스트 해본 결과, greater<pair<int,int>> 를 사용한 경우가 시간이 더 높게 측정 되었다. 

 

해결 코드: priority_queue<pair<int,int>> pq ; 

이와 같은 방식으로 우선 순위 큐를 선언한 후, Weight 값을 음수로 첫 번째 요소에 넣어주어 구현을 하게 되면 시간 초과를 막을 수 있을 것이다. 

 

이를 코드로 옮기면 아래와 같다.