[11779] 최소비용 구하기 2

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

11779번: 최소비용 구하기 2

다익스트라 알고리즘 문제다. 스위프트의 경우 heap구현이 필요하다. Rhyno님이 구현한 heap을 사용하였다.

 

풀이

입력되는 간선의 최대개수가 100,000개, 노드의 개수가 1,000개 이기에 우선순위 큐가 필수이며 메모리 초과를 유도하는 테스트 케이스가 주어지기에 다익스트라 알고리즘에 대한 정확한 이해가 필요하다. 이번 문제를 통해 조금 더 다익스트라 알고리즘에 친해졌다.

 

다익스트라 알고리즘을 통해 최단거리를 구하는데, 최단거리를 나타내는 ans배열에는 (최단거리, 진입노드) 튜플 배열로 생성하여 정보를 담아낸다. 

마지막에는 ans배열을 통해 [ 도착지점 -> 출발지점 ] 역순으로 dfs탐색을 통해 경로와 거리를 출력해 준다.

 

예제를 기준으로 설명하면 다음과 같다.

출발지점의 가중치를 0으로 변경. 시작노드는 자기자신과 동일하게 갱신했다.

1번 노드에서 갈 수 있는 간선을 탐색하여 ans[next].cost > ans[curr].cost + map[curr][next].cost 비교연산을 통해 더 작은 가중치로 ans값을 갱신한다.

ans의 값 중 가중치가 가장 작은 값으로 갱신된 노드인 4번 노드를 탐색, 5번 노드의 값을 더 줄일 수 있으므로 갱신한다.

이후 방문하지 않은 노드 중 가중치가 가장 작은 값인 2번노드를 탐색, 하지만 더 작은 값이 없기에 방문처리만 해주고 다음 노드를 탐색한다.

남아 있는 노드 중 더 작은 가중치를 가진 3번 노드 탐색, 마찬가지로 값을 갱신하지 못한 채 방문처리를 하고 마지막 5번노드로 이동

마지막 노드를 탐색 후 갱신된 ans배열.

1	2	3	4	5
0 : 1	2 : 1	3 : 1	1 : 1	4 : 4

다익스트라 알고리즘의 특성상, 매 탐색마다 가중치가 가장 작은 노드부터 탐색하기에 목적 노드를 방문 완료되면, 해당 노드의 경로는 이미 최단 경로인 것을 확신할 수 있다. 문제에서는 항상 시작 지점과 도착 지점의 경로가 있음을 보장했고, 테스트 케이스에서는 시간 초과와 메모리 초과를 유도하는 입력 값이 주어지기에 도착 노드의 방문이 확인되면 곧바로 탐색을 중단하고 갱신된 ans 배열을 통해 dfs 탐색을 수행하면 된다.

 

정답 코드