[BOJ 1753] 최단경로
- 문제풀이
문제
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
출력
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 256MB |
풀이
이 문제는 방향 그래프에서 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 전형적인 단일 시작점 최단 경로(Single-Source Shortest Path) 문제이다. 모든 간선의 가중치가 양수이므로 최단경로 :: 다익스트라 알고리즘을 사용하여 해결할 수 있다.
정점의 수 $V$가 최대 $20\,000$개, 간선의 수 $E$가 최대 $300\,000$개로 주어지므로, 일반적인 $O(V^2)$ 방식으로는 시간 제한을 통과할 수 없다. 따라서 우선순위 큐를 활용하여 $O(E \log V)$의 시간 복잡도를 가지는 효율적인 다익스트라 알고리즘을 구현하였다.
알고리즘의 주요 단계는 다음과 같다:
- 데이터 구조: 메모리 효율을 위해 인접 리스트를 사용하여 그래프 정보를 저장한다. 또한 최단 거리 정보를 저장할 배열을 충분히 큰 값($987\,654\,321$)으로 초기화한다.
- 초기화: 시작 정점의 최단 거리를 $0$으로 설정하고, 우선순위 큐에 삽입한다.
- 탐색 및 완화(Relaxation): 큐에서 거리가 가장 짧은 노드를 꺼내고, 해당 노드를 거쳐 이웃 노드로 가는 거리가 기존에 알고 있던 최단 거리보다 짧은지 확인한다. 만약 짧다면 최단 거리를 갱신하고 다시 큐에 삽입한다.
- 중복 처리: 큐에서 꺼낸 거리 값이 이미 저장된 최단 거리보다 크다면, 이미 처리된 경로이므로 무시한다.
최종적으로 계산된 거리 값이 초기값($987\,654\,321$) 그대로라면 도달할 수 없는 경로이므로 INF를 출력하고, 그렇지 않다면 최단 경로 값을 출력한다.
소스코드
Github Link : Source Code
참고 알고리즘 : 최단경로 :: 다익스트라 알고리즘, 우선순위 큐