https://www.acmicpc.net/problem/11779
11779번: 최소비용 구하기 2
첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스
www.acmicpc.net
다익스트라 알고리즘 문제다. 스위프트의 경우 heap구현이 필요하다. Rhyno님이 구현한 heap을 사용하였다.
풀이
입력되는 간선의 최대개수가 100,000개, 노드의 개수가 1,000개 이기에 우선순위 큐가 필수이며 메모리 초과를 유도하는 테스트 케이스가 주어지기에 다익스트라 알고리즘에 대한 정확한 이해가 필요하다. 이번 문제를 통해 조금 더 다익스트라 알고리즘에 친해졌다.
다익스트라 알고리즘을 통해 최단거리를 구하는데, 최단거리를 나타내는 ans배열에는 (최단거리, 진입노드) 튜플 배열로 생성하여 정보를 담아낸다.
마지막에는 ans배열을 통해 [ 도착지점 -> 출발지점 ] 역순으로 dfs탐색을 통해 경로와 거리를 출력해 준다.
예제를 기준으로 설명하면 다음과 같다.
| 1 | 2 | 3 | 4 | 5 |
| 0 : 1 | 2 : 1 | 3 : 1 | 1 : 1 | 4 : 4 |
다익스트라 알고리즘의 특성상, 매 탐색마다 가중치가 가장 작은 노드부터 탐색하기에 목적 노드를 방문 완료되면, 해당 노드의 경로는 이미 최단 경로인 것을 확신할 수 있다. 문제에서는 항상 시작 지점과 도착 지점의 경로가 있음을 보장했고, 테스트 케이스에서는 시간 초과와 메모리 초과를 유도하는 입력 값이 주어지기에 도착 노드의 방문이 확인되면 곧바로 탐색을 중단하고 갱신된 ans 배열을 통해 dfs 탐색을 수행하면 된다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [10830] 행렬 제곱 (0) | 2023.02.11 |
|---|---|
| [2638] 치즈 (0) | 2023.02.10 |
| [11444] 피보나치 수 6 (0) | 2023.02.08 |
| [17144] 미세먼지 안녕! (0) | 2023.02.07 |
| [4836] 춤 (0) | 2023.02.06 |