1️⃣ 최단 경로 알고리즘 개요
먼저 3가지 알고리즘의 차이부터 정리하면
| 알고리즘 | 시작점 | 음수 간선 | 음수 사이클 탐지 | 시간복잡도 |
|---|---|---|---|---|
| 다익스트라 | 단일 출발 | ❌ 불가 | ❌ | O(E log V) |
| 벨만-포드 | 단일 출발 | ✅ 가능 | ✅ 탐지 가능 | O(VE) |
| 플로이드-워셜 | 모든 쌍 | ✅ 가능 | ❌ | O(V³) |
가중치 전부 양수 + 단일 출발 → 다익스트라
음수 간선 있음 + 단일 출발 → 벨만 포드
모든 쌍 최단 거리 필요 → 플로이드 워셜
2️⃣ 다익스트라 (Dijkstra)
개념
시작점에서 모든 정점까지의 최단 거리를 구함. 핵심은 우선순위 큐(최소 힙) 로 "현재 가장 가까운 정점"을 먼저 처리하는 것.
🗺️ 비유: 네비게이션이 현재 위치에서 가장 빠른 길을 실시간으로 갱신하는 것.
음수 도로(역방향 이동)는 존재하지 않는다는 전제.
구현
import heapq
import sys
input = sys.stdin.readline
INF = float('inf')
def dijkstra(graph, start, n):
dist = [INF] * (n + 1)
dist[start] = 0
pq = [(0, start)] # (거리, 노드)
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]: # 이미 더 짧은 경로로 처리된 경우 스킵
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
return dist
# 사용 예시
n, e = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(e):
u, v, w = map(int, input().split())
graph[u].append((v, w))
start = int(input())
dist = dijkstra(graph, start, n)
⚠️
if d > dist[u]: continue이게 왜 필요하냐?
같은 노드가 큐에 여러 번 들어갈 수 있음.
이미 더 짧은 경로로 확정된 노드는 또 처리할 필요 없으니 스킵.
다익스트라 흐름 시각화
그래프: 1→2(2), 1→3(5), 2→3(1), 2→4(3), 3→4(1)
시작: 1
초기: dist = [INF, 0, INF, INF, INF]
pq = [(0, 1)]
1단계: (0, 1) 꺼냄
1→2: dist[2] = 2, pq에 (2,2)
1→3: dist[3] = 5, pq에 (5,3)
2단계: (2, 2) 꺼냄
2→3: dist[3] = min(5, 2+1) = 3, pq에 (3,3)
2→4: dist[4] = 5, pq에 (5,4)
3단계: (3, 3) 꺼냄
3→4: dist[4] = min(5, 3+1) = 4, pq에 (4,4)
최종: dist = [INF, 0, 2, 3, 4]
3️⃣ 벨만-포드 (Bellman-Ford)
개념
음수 간선이 있어도 최단 경로를 구할 수 있음. V-1번 반복으로 모든 간선을 완화(relax). V번째 반복에서도 갱신된다면 음수 사이클 존재.
⏰ 비유: 타임머신 문제. 시간을 되돌릴 수 있는(음수) 버스가 있을 때 최단 시간 구하기.
구현
INF = float('inf')
def bellman_ford(edges, start, n):
dist = [INF] * (n + 1)
dist[start] = 0
# V-1번 반복
for i in range(n - 1):
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# V번째 반복 - 갱신되면 음수 사이클 존재
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
return None # 음수 사이클 있음
return dist
# 사용 예시
n, m = map(int, input().split())
edges = []
for _ in range(m):
a, b, c = map(int, input().split())
edges.append((a, b, c))
result = bellman_ford(edges, 1, n)
if result is None:
print(-1) # 음수 사이클
다익스트라 vs 벨만-포드
음수 간선 없음 → 다익스트라 (훨씬 빠름, O(E log V)) 음수 간선 있음 → 벨만-포드 (느리지만 정확, O(VE)) 음수 사이클 탐지 필요 → 벨만-포드만 가능
4️⃣ 플로이드-워셜 (Floyd-Warshall)
개념
모든 쌍(A→B) 의 최단 거리를 한 번에 구함. "경유지 k를 거쳐서 가는 게 더 짧지 않냐?" 를 모든 k에 대해 반복.
🔄 핵심 점화식:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
"i에서 j로 직접 가는 것 vs k를 경유해서 가는 것"
구현
INF = float('inf')
def floyd_warshall(n, edges):
dist = [[INF] * (n + 1) for _ in range(n + 1)]
# 자기 자신은 0
for i in range(n + 1):
dist[i][i] = 0
# 간선 초기화
for u, v, w in edges:
dist[u][v] = min(dist[u][v], w) # 중복 간선 처리
# 플로이드-워셜 핵심: 경유지 k
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
⚠️ 주의사항
- 루프 순서: k가 가장 바깥 에 있어야 함
- 같은 구간에 여러 간선 있으면
min으로 초기화- n이 크면 O(n³)이라 n ≤ 500 수준에서만 사용
5️⃣ 트리 순회 & LCA
트리 순회 3가지
def preorder(node): # 전위: 루트 - 왼쪽 - 오른쪽
if node is None: return
visit(node)
preorder(node.left)
preorder(node.right)
def inorder(node): # 중위: 왼쪽 - 루트 - 오른쪽 (BST에서 정렬된 순서!)
if node is None: return
inorder(node.left)
visit(node)
inorder(node.right)
def postorder(node): # 후위: 왼쪽 - 오른쪽 - 루트 (파일 삭제, 수식 계산)
if node is None: return
postorder(node.left)
postorder(node.right)
visit(node)
LCA (Lowest Common Ancestor, 최소 공통 조상)
두 노드의 공통 조상 중 가장 깊은 노드를 찾는 것.
🌳 비유: 가족 관계에서 두 사람의 가장 가까운 공통 조상 찾기.
import sys
from collections import deque
sys.setrecursionlimit(10**6)
def lca_naive(u, v, depth, parent):
# 깊이를 맞춤
while depth[u] > depth[v]:
u = parent[u]
while depth[v] > depth[u]:
v = parent[v]
# 같은 노드가 될 때까지 같이 올라감
while u != v:
u = parent[u]
v = parent[v]
return u
def build_tree(graph, root, n):
depth = [0] * (n + 1)
parent = [0] * (n + 1)
visited = [False] * (n + 1)
queue = deque([root])
visited[root] = True
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if not visited[neighbor]:
visited[neighbor] = True
depth[neighbor] = depth[node] + 1
parent[neighbor] = node
queue.append(neighbor)
return depth, parent
💡 Naive LCA는 O(depth) 라 트리가 편향되면 느림.
대회에서는 희소 테이블(Sparse Table) 을 이용한 O(log N) LCA를 씀.
6️⃣ Union-Find (분리 집합)
개념
여러 개의 집합을 관리하며 합치기(Union) 와 같은 집합인지 확인(Find) 을 빠르게 수행. 크루스칼 MST에서 사이클 판별에 핵심적으로 사용됨.
📦 비유: 여러 팀이 있을 때 두 사람이 같은 팀인지 확인하고, 두 팀을 합치는 연산.
구현 (경로 압축 + 랭크 최적화)
class UnionFind:
def __init__(self, n):
self.parent = list(range(n + 1))
self.rank = [0] * (n + 1)
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 경로 압축!
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False # 이미 같은 집합 (사이클!)
# 랭크 기반 합치기 (트리 높이 균형 유지)
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
uf = UnionFind(5)
uf.union(1, 2)
uf.union(3, 4)
print(uf.find(1) == uf.find(2)) # True (같은 집합)
print(uf.find(1) == uf.find(3)) # False (다른 집합)
uf.union(2, 3)
print(uf.find(1) == uf.find(4)) # True (이제 같은 집합)
💡 경로 압축(Path Compression):
find를 호출할 때 루트까지 올라가면서 중간 노드들을 전부 루트에 직접 연결.
이후find가 거의 O(1)처럼 동작함.
7️⃣ MST (최소 신장 트리)
개념
그래프의 모든 정점을 연결하는 트리 중 간선 가중치의 합이 최소인 트리. N개의 정점을 N-1개의 간선으로 연결.
🏗️ 비유: 여러 도시를 최소 비용으로 도로를 연결해서 전부 이동 가능하게 만들기.
크루스칼 (Kruskal) - O(E log E)
간선을 가중치 오름차순으로 정렬하고, 사이클을 만들지 않는 간선을 선택. Union-Find로 사이클 여부를 O(α(n))에 판별.
def kruskal(n, edges):
uf = UnionFind(n)
edges.sort(key=lambda x: x[2]) # 가중치 기준 정렬
mst_cost = 0
mst_edges = []
for u, v, w in edges:
if uf.union(u, v): # 사이클이 생기지 않으면
mst_cost += w
mst_edges.append((u, v, w))
if len(mst_edges) == n - 1: # n-1개 선택하면 완료
break
return mst_cost, mst_edges
# 사용 예시
n, m = map(int, input().split())
edges = []
for _ in range(m):
a, b, c = map(int, input().split())
edges.append((a, b, c))
cost, _ = kruskal(n, edges)
print(cost)
크루스칼 흐름:
간선: (1,2,1), (2,3,2), (1,3,3), (3,4,4) (1,2,1) 선택 - 사이클 없음 ✅ (2,3,2) 선택 - 사이클 없음 ✅ (1,3,3) 스킵 - 1,2,3 이미 연결됨 (사이클!) ❌ (3,4,4) 선택 - 사이클 없음 ✅ MST 비용: 1+2+4 = 7
프림 (Prim) - O(E log V)
하나의 정점에서 시작해서 MST에 포함된 정점과 인접한 간선 중 최솟값을 선택. 다익스트라와 구조가 유사함.
import heapq
def prim(graph, start, n):
visited = [False] * (n + 1)
pq = [(0, start)] # (가중치, 노드)
total = 0
while pq:
w, u = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
total += w
for v, weight in graph[u]:
if not visited[v]:
heapq.heappush(pq, (weight, v))
return total
크루스칼 vs 프림 - 언제 뭘 씀?
간선이 적은 경우 (희소 그래프) → 크루스칼 (간선 정렬이 핵심) 간선이 많은 경우 (밀집 그래프) → 프림 (정점 중심으로 확장) 코테에서는 구현이 더 간단한 크루스칼을 더 많이 씀.
8️⃣ 알고리즘 선택 기준 토론
최단 경로 - 뭘 쓸지
단일 출발 + 양수 간선 + 빠른 속도 필요 → 다익스트라 단일 출발 + 음수 간선 존재 → 벨만-포드 단일 출발 + 음수 사이클 탐지 필요 → 벨만-포드 모든 쌍 최단 경로 + n ≤ 500 → 플로이드-워셜 모든 쌍인데 n이 크면 → 각 정점에서 다익스트라 반복
MST - 뭘 쓸지
간선 수 적음 (m ≤ n log n 수준) → 크루스칼 간선 수 많음 (완전 그래프에 가까움) → 프림 구현 편의성 → 크루스칼
Union-Find가 필요한 신호
"두 노드가 연결되어 있냐?" → find(x) == find(y) "사이클이 생기냐?" → union 시 이미 같은 집합이면 사이클 "그룹 수를 세라" → union 후 루트 개수
📝 8주차 핵심 요약
✅ 다익스트라
- 단일 출발, 양수 간선, O(E log V)
- 우선순위 큐 + visited 스킵 패턴
✅ 벨만-포드
- 단일 출발, 음수 간선 O(VE)
- V-1번 relax, V번째에 갱신되면 음수 사이클
✅ 플로이드-워셜
- 모든 쌍, O(V³), k 루프가 가장 바깥
- dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
✅ Union-Find
- find: 경로 압축 → 거의 O(1)
- union: 랭크 기반 → 트리 균형 유지
- 크루스칼 사이클 판별에 필수
✅ MST
- 크루스칼: 간선 정렬 + Union-Find
- 프림: 다익스트라 구조 + 정점 중심 확장
- 코테에서는 크루스칼이 더 자주 쓰임