다익스트라 (Dijkstra)

관련 문제

문제	난이도	핵심
배달	Lv.2	다익스트라 기본
합승 택시 요금	Lv.3	다익스트라 응용
경주로 건설	Lv.3	다익스트라 + 격자

---

1. 개념

다익스트라는 하나의 시작점에서 모든 노드까지의 최단거리를 구하는 알고리즘이다.

음수 가중치가 없는 그래프에서만 사용할 수 있다.

      2
  A ——— B
  |     |
3 |     | 1
  |     |
  C ——— D
      4

A에서 D까지 최단경로?
A → B → D = 2 + 1 = 3  ✅
A → C → D = 3 + 4 = 7  ❌

---

2. 동작 과정

시작점 A에서 모든 노드까지의 최단거리

단계	현재 노드	dist[A]	dist[B]	dist[C]	dist[D]
초기	-	0	∞	∞	∞
1	A	0	2	3	∞
2	B	0	2	3	3
3	D	0	2	3	3
4	C	0	2	3	3

매 단계에서 아직 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택해서 인접 노드의 거리를 갱신한다.

---

3. 핵심 사용 패턴

우선순위 큐 활용

매번 최단거리 노드를 찾는 게 핵심인데, 우선순위 큐(최소 힙)를 쓰면 O(log N)으로 빠르게 찾을 수 있다.

1. 시작점의 거리를 0으로 초기화, 나머지는 ∞
2. 우선순위 큐에 (거리, 노드) 삽입
3. 큐에서 거리가 가장 짧은 노드 꺼냄
4. 인접 노드의 거리 갱신 (현재 거리 + 간선 가중치 < 기존 거리면 갱신)
5. 큐가 빌 때까지 반복

---

4. 핵심 포인트 2가지

음수 가중치가 있으면 쓸 수 없다

다익스트라는 현재까지의 최단거리가 앞으로도 최단거리라는 가정을 기반으로 한다. 음수 가중치가 있으면 이 가정이 깨진다. 음수 가중치가 있는 경우엔 벨만-포드 알고리즘을 써야 한다.

이미 처리된 노드는 건너뛰어라

우선순위 큐에서 꺼낸 노드의 거리가 현재 저장된 최단거리보다 크면 이미 더 짧은 경로로 처리된 것이므로 건너뛴다.

if (큐에서 꺼낸 거리 > dist[node]) continue;

---

5. 시간복잡도

구현 방식	시간복잡도	비고
단순 배열	O(V²)	V = 노드 수
우선순위 큐	O((V + E) log V)	E = 간선 수, 코테 표준

코테에서는 우선순위 큐 방식을 쓴다.

---

6. 주의사항

• 음수 가중치 있으면 사용 불가. 벨만-포드로 풀어야 한다.
• 초기 거리를 충분히 크게 설정해라. Integer.MAX_VALUE나 987654321처럼 충분히 큰 값으로 초기화해라.
• 이미 처리된 노드는 건너뛰어라. 우선순위 큐에서 꺼낸 거리가 현재 최단거리보다 크면 무시해야 한다.
• 단방향/양방향 간선을 구분해라. 문제에서 양방향이면 양쪽 다 간선을 추가해야 한다.