[5719] 거의 최단 경로

https://www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

다익스트라 알고리즘 문제다. 런타임 에러를 만나 고생했다.

 

풀이

접근방법에 대해 간략하게 이야기하면 다음 흐름과 같다.

1. 다익스트라 알고리즘을 통해 시작노드 S부터 각 노드까지의 최단거리를 구해놓은 뒤,
2. 도착노드 D부터 시작노드 S까지 그래프 탐색을 통해 해당 경로가 최단경로임이 확인되면 해당 경로를 삭제
   (여기서 1에서 구한 최단경로 비용이 사용된다.)
3. 최단 경로가 삭제된 상태의 그래프를 다익스트라 알고리즘을 수행하여 거의 최단 경로를 구해내면 된다.

2번 과정이 이번 문제의 핵심이라고 생각한다. 우선 그래프가 방향이 정해져 있는 지향그래프이기에, 그래프 탐색을 위해 간선정보를 입력받을 때, 역탐색을 위한 rev배열을 생성하여 따로 저장해 놓는다. 배열의 경우 [[(node:Int, cost:Int)]]() 형태의 튜플 배열로 저장하여 다음 노드의 번호와 비용을 저장.

 

D -> S 역탐색을 수행할 때, 해당 경로가 최단경로임을 확인하는 방법은 다음과 같다. 여기서 1번 과정에서 구한 최단비용이 사용된다.

(D에서 해당 노드까지의 탐색비용 + S에서 해당 노드까지의 최단 비용) == (S에서 D까지의 최단비용)

 

여기서 최단경로임이 확인되면, 해당 경로를 삭제한 뒤 해당노드에서 다음 탐색을 이어가면 된다. 경로 삭제를 표현하는 방법은 많겠지만, 본인의 경우 해당 노드의 인덱스를 -1로 수정하여 삭제된 경로임을 표시하였다.

 

이후 수정된 그래프를 기준으로 다익스트라 알고리즘을 수행하면 거의 최단 경로를 구할 수 있다.

 

주의할 점

8%에서 런타임 에러를 뿜어대길래 반례를 찾느라 헤맸다. 다익스트라 알고리즘을 수행할 때, INF를 생각 없이 Int.max로 설정하여 오버플로우가 발생했었다. 즉 1번에서 얻은 최단 경로값에 Int.max가 있었고, 이걸 2번 과정에서 최단경로인지 확인할 때, D에서 해당 노드의 탐색비용 + Int.max의 연산이 수행되니 오버플로우가 발생했던 것. 따라서 (N의 최댓값 500 * 비용의 최댓값 1,000) 여기에 조금 더 여유를 둬서 INF를 5,000,000으로 설정하여 다익스트라를 수행하였더니 통과하였다. 백준의 경우 스위프트는 어떤 오류던지 무조건 런타임 에러를 반환하기에 원인을 찾는데 조금 고생했다. 그래도 이렇게 힘들게 문제를 해결하면 성취감이 몰려온다. 이런 매력에 PS를 하는 게 아닌가 싶다.

 

정답 코드