[Graph Algorithms] Dijkstra + Kruskal + Prim + Union-Find

1. 최단 경로 문제 개요

그래프에서 두 정점 사이의 가장 짧은 거리(비용)를 구하는 문제

대표 알고리즘

• BFS: 모든 간선 가중치 = 1일 때 최단 거리
• Dijkstra: 양수 가중치 일반 그래프
• Bellman-Ford: 음수 가중치 가능
• Floyd-Warshall: 모든 쌍 최단 경로

---

2. 다익스트라(Dijkstra)

아이디어

• “가까운 정점부터 하나씩 확정”하는 탐욕적(Greedy) 알고리즘

• 핵심 구조:

  • dist[]: 시작점에서의 최단 거리 테이블
  • 우선순위 큐(heapq): 아직 확정되지 않은 정점 중 가장 짧은 거리 뽑기

수도코드

dist[] = INF
dist[start] = 0
PQ = (0, start)

while PQ not empty:
    d, u = PQ.pop()
    if d > dist[u]: continue
    for (v, w) in adj[u]:
        if dist[v] > d + w:
            dist[v] = d + w
            PQ.push((dist[v], v))

파이썬 구현

import heapq
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
start = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

INF = int(1e9)
dist = [INF]*(N+1)

def dijkstra(s):
    dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:  # 이미 더 짧은 거리로 확정된 경우 skip
            continue
        for v, w in graph[u]:
            if dist[v] > d + w:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))

dijkstra(start)
for i in range(1, N+1):
    print(dist[i] if dist[i] != INF else "INF")

---

3 최소 신장 트리(MST)

개념

• 그래프의 모든 정점을 사이클 없이 연결하는 최소 비용 부분 그래프

• 간선 수는 항상 $N-1$

• 대표 알고리즘

  • Kruskal: 간선 정렬 + 유니온 파인드
  • Prim: 시작 정점에서부터 확장 (다익스트라와 유사)

---

4 유니온 파인드 (Disjoint Set Union)

아이디어

• 여러 원소들을 “집합 단위”로 관리하는 자료구조

• 핵심 연산

  1. find(x): 원소 x의 대표(루트) 찾기
  2. union(a, b): 두 집합을 합침

기본 구조

parent = [i for i in range(N+1)]

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])   # 경로 압축(Path Compression)
    return parent[x]

def union(a, b):
    ra, rb = find(a), find(b)
    if ra != rb:
        if ra < rb: parent[rb] = ra   # union by rank/size 가능
        else: parent[ra] = rb

특징

• 경로 압축: find를 할 때 트리를 납작하게 만들어 탐색 속도 향상
• union by rank/size: 작은 트리를 큰 트리에 붙여 효율성 확보
• 시간 복잡도는 거의 상수: $O(\alpha(N))$, α=아커만 함수 역함수 (매우 작음)

---

5. Kruskal MST

아이디어

1. 모든 간선을 비용 기준 정렬
2. 낮은 비용부터 하나씩 채택
3. 사이클 여부를 유니온 파인드로 판별
4. 간선 N-1개 선택 시 종료

코드

edges = []
for _ in range(M):
    u, v, w = map(int, input().split())
    edges.append((w, u, v))

edges.sort()
parent = [i for i in range(N+1)]

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    ra, rb = find(a), find(b)
    if ra != rb:
        if ra < rb: parent[rb] = ra
        else: parent[ra] = rb
        return True
    return False

mst_cost = 0
for w, u, v in edges:
    if union(u, v):   # 사이클 없는 간선만 선택
        mst_cost += w

print(mst_cost)

---

6. Prim MST

아이디어

• 다익스트라처럼 PQ를 사용해 “아직 방문하지 않은 정점 중 가장 가까운 정점”을 확장

코드

import heapq

def prim(start, graph, N):
    visited = [False]*(N+1)
    pq = [(0, start)]   # (비용, 정점)
    total = 0
    count = 0
    while pq and count < N:
        w, u = heapq.heappop(pq)
        if visited[u]: continue
        visited[u] = True
        total += w
        count += 1
        for v, cost in graph[u]:
            if not visited[v]:
                heapq.heappush(pq, (cost, v))
    return total

---

7. 알고리즘 비교

알고리즘	목적	탐색 방식	자료구조	특징
Dijkstra	최단 경로	가까운 정점부터 거리 확정	PQ(힙)	가중치 양수
Kruskal	MST	간선 정렬 + 유니온 파인드	정렬 + DSU	희소 그래프 유리
Prim	MST	PQ로 정점 확장	PQ(힙)	밀집 그래프 유리

---

8. 추천 백준 문제

• 다익스트라

  • 1753 최단경로
    → 방향 그래프 + 양수 가중치, 다익스트라 기본 연습
  • 1916 최소비용 구하기
    → 두 정점 사이 최단 비용, 다익스트라 단일 쿼리 실습

• MST

  • 1197 최소 스패닝 트리
    → 크루스칼 기본, 유니온 파인드 연습 필수
  • 1922 네트워크 연결
    → 모든 컴퓨터 연결 비용 최소화, MST 응용
  • 4386 별자리 만들기
    → 좌표 거리 계산 + MST 결합, 실전 난이도 상승

---