문제
방향 그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 문제이다. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 둘째 줄에 시작 정점 번호 K가 주어진다. (1 ≤ K ≤ V) 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 정수 u, v, w가 주어진다. u에서 v로 가는 가중치 w인 간선이다. (1 ≤ w ≤ 10)
출력
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로 거리를 출력한다. 시작점 자신은 0, 경로가 없으면 INF를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 6 1 5 1 1 1 2 2 1 3 3 2 3 4 2 4 5 3 4 6 | 0 2 3 7 INF |
풀이
다익스트라(Dijkstra) 알고리즘을 우선순위 큐(최소 힙)로 구현한다.
- 인접 리스트로 그래프를 구성한다
- 시작 정점의 거리를 0, 나머지는 INF로 초기화한다
- 우선순위 큐에
(시작 정점, 거리 0)을 넣는다 - 큐에서 현재 최소 거리 정점을 꺼낸다
- 이미 처리된 정점(저장된 거리보다 큰 거리)이면 스킵
- 인접 정점들에 대해
현재 거리 + 간선 가중치가 기존 거리보다 작으면 갱신 후 큐에 추가 - 큐가 빌 때까지 반복하면 모든 정점의 최단 거리가 확정된다
- INF인 정점은 "INF"로, 그 외는 거리를 출력
핵심 아이디어: 우선순위 큐를 이용한 다익스트라 알고리즘으로, 이미 방문한 정점은 조기 스킵하여 효율적으로 최단 경로를 계산한다.
코드
package com.ssafy.an.day199;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Day155BOJ1753다익스트라구현 {
private static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(br.readLine());
List<List<Node>> list = new ArrayList<>(V + 1);
for (int i = 0; i <= V; i++) {
list.add(new ArrayList<Node>());
}
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
list.get(from).add(new Node(to, weight));
}
int[] dist = new int[V + 1];
Arrays.fill(dist, INF);
dist[start] = 0;
PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.add(new Edge(start, 0));
while (!pq.isEmpty()) {
Edge cur = pq.poll();
if (dist[cur.no] < cur.dist)
continue;
for (Node curNode : list.get(cur.no)) {
int to = curNode.to;
int addDist = curNode.w;
if (dist[to] > dist[cur.no] + addDist) {
dist[to] = dist[cur.no] + addDist;
pq.add(new Edge(to, dist[to]));
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= V; i++) {
sb.append(dist[i] == INF ? "INF" : dist[i]).append("\n");
}
System.out.print(sb.toString());
}
static class Node {
int to, w;
public Node(int to, int w) {
this.to = to;
this.w = w;
}
}
static class Edge implements Comparable<Edge> {
int no, dist;
public Edge(int no, int dist) {
super();
this.no = no;
this.dist = dist;
}
@Override
public int compareTo(Edge o) {
return dist - o.dist;
}
}
}복잡도
- 시간: O((V + E) log V)
- 공간: O(V + E)