주제 13: 최단 경로 알고리즘
요약
본 문서는 그래프 이론의 핵심 주제인 최단 경로 알고리즘을 다룹니다. 간선 가중치에 따라 BFS, Dijkstra, Bellman-Ford 등 적절한 알고리즘 선택이 중요하며, 특히 비가중치와 음수 가중치 처리 방식에 대한 이해를 강조합니다.
핵심 포인트
- 비가중치 그래프는 BFS로 최단 경로를 찾습니다. (O(V+E))
- 음이 아닌 가중치는 Dijkstra 알고리즘을 사용해야 합니다.
- 음수 간선이 포함되면 Bellman-Ford 알고리즘이 필요합니다.
- Dijkstra의 핵심은 '완화(relaxation)' 과정을 통해 최적 거리를 갱신하는 것입니다.
이제 그래프에 대해 더 깊이 들어가 보겠습니다.
핵심 면접 질문은 다음과 같습니다:
그래프가 주어졌을 때, 한 노드에서 다른 노드까지의 최소 비용 경로를 어떻게 찾습니까?
적절한 알고리즘은 주로 **간선 가중치(edge weights)**에 따라 달라집니다.
1. 먼저: 어떤 알고리즘을 사용해야 할까요?
이 표를 암기하세요:
| 그래프 | 알고리즘 |
|---|---|
| 비가중치 그래프 (Unweighted graph) | BFS |
| ... |
면접에서 가장 중요합니다
비가중치 → BFS
음이 아닌 가중치(Non-negative weighted) → Dijkstra
음수 간선(Negative edges) → Bellman-Ford
2. 비가중치 최단 경로 (Unweighted Shortest Path)
이는 이미 BFS를 통해 보셨습니다.
예시:
0 --- 1 --- 2
|
3
모든 간선은 동일한 비용을 가집니다.
0에서 시작하여:
distance[0] = 0
distance[1] = 1
distance[2] = 2
...
BFS를 사용합니다:
from collections import deque
def shortest_path(graph, start):
...
복잡도 (Complexity)
시간: O(V + E)
공간: O(V)
3. BFS가 가중치 그래프에서 작동하지 않는 이유
다음 것을 고려해 보세요:
A --10-- B
\ |
1 1
...
간선은 더 많지만 총 비용이 낮은 경로가 있을 수 있습니다.
BFS는 다음을 최소화합니다:
간선의 개수 (number of edges)
다음이 아닙니다:
총 가중치 (total weight)
가중치 그래프의 경우, 다른 알고리즘이 필요합니다.
4. Dijkstra의 알고리즘 ⭐
Dijkstra는 다음 조건일 때 최단 경로를 찾습니다:
모든 간선 가중치가 음이 아닌(non-negative) 값일 때.
예시:
4
A -------- B
| |
...
A에서 시작하여:
A = 0
C = 1
B = 4
...
5. Dijkstra의 핵심 아이디어
모든 노드까지 알려진 최적 거리를 유지합니다.
초기에는:
start = 0
나머지 모든 값 = 무한대 (infinity)
그런 다음 반복적으로 수행합니다:
- 처리되지 않은 노드 중 가장 작은 거리를 가진 것을 선택합니다.
- 그 노드의 이웃들을 검사합니다.
- 이들의 거리를 개선하려고 시도합니다.
이 연산을 **완화(relaxation)**라고 합니다.
6. 완화 (Relaxation)
다음과 같다고 가정해 봅시다:
A --5--> B
그리고:
distance[A] = 3
그렇다면 A를 거쳐 가는 경로는 다음과 같은 비용이 듭니다:
3 + 5 = 8
만약:
distance[B] = 10
이었다면, 우리는 이를 개선합니다:
distance[B] = 8
코드로 표현하면:
new_distance = distance + weight
if new_distance < dist[neighbor]:
...
이것이 Dijkstra의 핵심입니다.
7. heapq를 사용한 Dijkstra
Python의 heapq는 Dijkstra에 완벽합니다.
그래프 형식:
graph = {
0: [(1, 4), (2, 1)],
1: [(3, 1)],
...
각 튜플은 다음을 의미합니다:
(이웃 노드, 가중치)
구현:
import heapq
def dijkstra(graph, start):
...
8. 가장 중요한 Dijkstra 라인
다음 라인은:
if current_dist > dist[node]:
continue
극도로 중요합니다.
왜냐하면?
heapq는 직접적인 decrease-key 연산을 제공하지 않기 때문입니다.
대신, 같은 노드에 대해 여러 항목을 푸시할 수 있습니다.
예시:
(10, B)
(7, B)
(5, B)
(5, B)가 처리될 때, 이전 항목들은 오래된 것이 됩니다 (stale).
따라서:
if current_dist > dist[node]:
continue
이러한 항목들을 무시합니다.
9. Dijkstra 복잡도
인접 리스트 + 이진 힙을 사용하면:
시간: O((V + E) log V)
보통 다음으로 간소화됩니다:
O(E log V)
공간:
O(V + E)
10. Dijkstra는 음수 가중치를 처리할 수 없음
예시:
A --2--> B
A --5--> C
C --(-10)--> B
경로:
A → C → B
의 비용은 다음과 같습니다:
5 + (-10) = -5
음수 간선은 Dijkstra의 탐욕적 가정(greedy assumption)을 깨뜨릴 수 있습니다.
따라서:
음수 간선?
↓
Dijkstra 사용 금지
적절할 때는 Bellman-Ford를 사용하십시오.
11. Bellman-Ford
Bellman-Ford는 다음을 처리할 수 있습니다:
- 양수 간선
- 0 가중치 간선
- 음수 간선
또한 소스에서 도달 가능한 **음수 사이클(negative cycles)**도 감지할 수 있습니다.
기본 아이디어
모든 간선을 반복적으로 완화(Relax)합니다.
V개의 정점에 대해 다음을 수행합니다:
V - 1
왜 V - 1인가요?
최단 단순 경로(shortest simple path)는 최대 V - 1개의 간선을 포함할 수 있기 때문입니다.
12. Bellman-Ford 구현
다음과 같다고 가정합시다:
edges = [
(0, 1, 4),
(0, 2, 5),
...
각 간선은 다음과 같습니다:
(출발지, 도착지, 가중치)
구현:
def bellman_ford(n, edges, source):
dist = [float(
이 방법은 많은 일반 가중치 그래프 문제에서 다익스트라(Dijkstra)보다 느립니다.
따라서 벨만-포드(Bellman-Ford)를 무조건 사용해서는 안 됩니다.
**음수 간선(negative edges)**이 관련될 때 사용하세요.
# 14. 0-1 BFS
모든 간선의 가중치가 다음 중 하나일 경우 어떻게 할까요?
0 또는 1
예시:
A --0--> B
B --1--> C
다익스트라 대신 **0-1 BFS**를 사용할 수 있습니다.
이것은 `deque`를 사용합니다.
### 규칙
가중치가 0인 간선에 대해서는:
appendleft()
가중치가 1인 간선에 대해서는:
append()
## 템플릿
```python
from collections import deque
def zero_one_bfs(graph, start, n):
...
복잡도:
O(V + E)
15. 플로이드-워셜 (Floyd-Warshall)
지금까지 우리는 주로 다음을 찾아왔습니다:
하나의 시작점으로부터의 최단 경로.
만약 다음을 원한다면 어떨까요?
모든 정점 쌍 사이의 최단 경로?
**플로이드-워셜(Floyd-Warshall)**을 사용하세요.
이것은 동적 계획법(dynamic programming)을 사용합니다.
핵심 아이디어
다음과 같이 정의합시다:
dist[i][j]
이는 i에서 j까지 알려진 최단 거리를 나타냅니다.
모든 중간 노드 k에 대해:
dist[i][j] = min(
dist[i][j],
dist[i][k] + dist[k][j]
...
16. 플로이드-워셜 구현
def floyd_warshall(dist):
n = len(dist)
...
복잡도:
시간: O(V³)
공간: O(V²)
따라서, 비교적 작은 그래프에 일반적으로 적합합니다.
17. 플로이드-워셜을 이용한 음수 사이클 탐지
알고리즘 실행 후:
for i in range(n):
if dist[i][i] < 0:
print(
times = [
[2, 1, 1],
[2, 3, 1],
...
의미:
2 → 1 (비용 1)
2 → 3 (비용 1)
3 → 4 (비용 1)
노드 `2`에서 시작할 경우:
2 → 1 = 1
2 → 3 = 1
2 → 3 → 4 = 2
따라서 신호를 받는 데 필요한 시간은 다음과 같습니다:
max(1, 1, 2) = 2
패턴은 다음과 같습니다:
Dijkstra
↓
모든 노드까지의 최단 거리
...
# 20. 중요 문제: K 스톱 내 가장 저렴한 항공권 (Cheapest Flights Within K Stops)
이 문제는 더 까다롭습니다.
제한 사항이 있습니다:
최대 K 스톱
노드당 최소 비용에만 기반한 일반적인 Dijkstra 구현은 불충분할 수 있습니다. 왜냐하면 너무 많은 스톱으로 노드에 저렴하게 도달하는 것이 유효한 상태가 아닐 수 있기 때문입니다.
상태는 다음과 같은 형태가 됩니다:
(비용, 노드, 스톱)
이것은 중요한 면접 교훈을 가르쳐 줍니다:
> 때로는 그래프의 상태가 단순히 노드 그 이상일 수 있습니다.
예를 들어:
(노드, 남은 단계)
(노드, 연료)
(노드, 정류장 수)
...
# 21. 최단 경로 인식 (Shortest Path Recognition)
이것은 매우 중요합니다.
### 질문에
### ❌ 가중치 간선(weighted edges)에 BFS 사용하기
BFS는 총 비용(total cost)이 아닌 간선의 개수(number of edges)를 최소화합니다.
### ❌ 음수 가중치(negative weights)와 Dijkstra 사용하기
Dijkstra 알고리즘은 음수가 아닌 간선 가중치를 필요로 합니다.
### ❌ 오래된 힙 항목(stale heap entries)을 잊지 않기
항상 다음 사항을 고려해야 합니다:
if current_dist > dist[node]:
continue
### ❌ 방향 그래프와 무방향 그래프 혼동하기
무방향 간선(undirected edge)의 경우:
graph[u].append((v, weight))
graph[v].append((u, weight))
방향 간선(directed):
graph[u].append((v, weight))
### ❌ 경로가 필요할 때 거리만 반환하기
다음 사항을 유지하고 나중에 경로를 재구성해야 합니다:
parent[neighbor] = node
# 25. 인터뷰 연습 문제 (Interview Practice)
### 쉬움 (Easy)
1. 가중치 없는 그래프(unweighted graph)에서의 최단 경로
2. 네트워크 지연 시간 (Network Delay Time)
3. 최소 노력으로 이동 가능한 경로 (Path With Minimum Effort)
### 중간 (Medium)
1. K 정거장 이내 가장 저렴한 항공권 (Cheapest Flights Within K Stops)
2. 상승하는 물 속 수영하기 (Swim in Rising Water)
3. 지점 연결에 필요한 최소 비용 (Minimum Cost to Connect Points)
4. 0-1 행렬 (0-1 Matrix)
5. 모서리에 도달하기 위한 최소 장애물 제거 (Minimum Obstacle Removal to Reach Corner)
### 어려움 (Advanced)
1. Bellman-Ford 구현
2. Floyd-Warshall 알고리즘
3. 상태 최적화를 이용한 가장 저렴한 항공권 (Cheapest Flights with state optimization)
4. 모든 노드를 방문하는 최단 경로 (Shortest Path Visiting All Nodes)
## 🧠 최종 치트 시트 (Final Cheat Sheet)
최단 경로 (SHORTEST PATH)
│
┌───────────┼───────────┐
...
**다음 주제: Union-Find (분리 집합 자료구조), 최소 신장 트리(Minimum Spanning Trees), Kruskal 및 Prim 알고리즘 — 또 다른 주요 인터뷰/시험 섹션입니다.**
AI 자동 생성 콘텐츠
본 콘텐츠는 Dev.to AI tag의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기