다익스트라 알고리즘 (Dijkstra Algorithm)
그래프에서 여러 개의 노드가 있을 때,
특정 정점에서 출발하여 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘
-
'음의 간선' 즉, 가중치가 0보다 작은 값이 아닌 경우에만 정상 동작한다.
-
현실 세계에서의 간선(길)의 가중치는 음수로 표현되지 않기 때문에, 다익스트라 알고리즘은 실제로
인공위성, GPS, 소프트웨어등에서 많이 사용된다. -
매번
'가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문에, 기본적으로 그리디 알고리즘으로 분류된다. -
인접행렬이나 인접리스트를 구해가는 과정에서
우선순위 큐(Priority Queue)를 이용해 최소값 기준으로 탐색하도록 해야 효율성이 올라간다.
문제 (백준 1446)
문제
매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.
세준이가 운전해야 하는 거리의 최솟값을 출력하시오.
입력
첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.
출력
세준이가 운전해야하는 거리의 최솟값을 출력하시오.
예제 입력 1
5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90예제 출력 1
70접근 방법
-
먼저, 그래프를 생성/초기화 시켜준다. (연결된 간선, 이동 비용)
-
일반 도로는 1 떨어진 곳은 1의 비용으로 이동할수 있으므로 초기화.
-
지름길 간선을 추가해준다. (단, 지름길이 더 효율적인 경우에만 추가해준다)
-
dist[]배열을 생성 후, 최대값으로 초기화시켜준다.dist[i]는 i 지점으로 이동하는 최소 비용이 저장될것이다.
-
우선순위 큐를 비용을 기준으로 오름차순 정렬하고, 모든 간선을 탐색할때까지 탐색한다.
다익스트라 동작 과정
- 시작점 0에서 출발, 비용 0
- 큐에 (0,0) 저장 → 꺼내서 탐색
-
0의 인접노드들:
- (1, 비용1) → dist[1] = 1, 큐에 (1,1) 추가
- (10, 비용5) → dist[10] = 5, 큐에 (10,5) 추가
-
큐에는 (1,1), (10,5) 두 개가 있음
- 다음으로 (1,1) 꺼내 탐색:
-
1의 인접노드 (2, 비용1) → dist[2] = 2, 큐에 (2,2) 추가
-
큐 상태: (2,2), (10,5)
- 다음으로 (2,2) 꺼내 탐색 → (3,3) 추가
-
이렇게 계속 1씩 증가하며 (3,3), (4,4), ... (9,9) 추가
-
큐 상태 (10,5), (3,3), (4,4), ... (9,9)
- 비용 5인 (10,5)가 (9,9)보다 먼저 나오게 됨 → 그래서 최단 거리는 5로 확정
-
일반 도로로 0→1→2→...→10 까지 가면 비용 10이지만, 다익스트라가 자동으로 비용 5짜리 지름길을 선택함
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class boj_1446 {
static int N, D;
static int[][] shortCuts;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
shortCuts = new int[N][3]; // [시작, 도착, 거리]
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
shortCuts[i][0] = Integer.parseInt(st.nextToken());
shortCuts[i][1] = Integer.parseInt(st.nextToken());
shortCuts[i][2] = Integer.parseInt(st.nextToken());
}
// 그래프: 위치별 인접 노드 리스트 (to, cost)
List<List<int[]>> graph = new ArrayList<>();
for (int i = 0; i <= D; i++) {
graph.add(new ArrayList<>());
}
// 기본 도로 간선 추가 (i -> i+1, cost 1)
for (int i = 0; i < D; i++) {
graph.get(i).add(new int[]{i + 1, 1});
}
// 지름길 추가 (to <= D && 지름길이 기존 거리보다 짧은 경우만)
for (int i = 0; i < N; i++) {
int from = shortCuts[i][0];
int to = shortCuts[i][1];
int dist = shortCuts[i][2];
if (to <= D && dist < (to - from)) {
graph.get(from).add(new int[]{to, dist});
}
}
int[] dist = new int[D + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{0, 0}); // {위치, 비용}
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int pos = cur[0];
int cost = cur[1];
if (dist[pos] < cost) continue;
for (int[] next : graph.get(pos)) {
int nextPos = next[0];
int nextDist = next[1];
if (dist[nextPos] > dist[pos] + nextDist) {
dist[nextPos] = dist[pos] + nextDist;
pq.offer(new int[]{nextPos, dist[nextPos]});
}
}
}
System.out.println(dist[D]);
}
}
