Graph Optimization Problems and Greedy Algorithms — MST, Dijkstra, 그리고 그리디

2026-06-06 Algorithm –

#greedy#optimization#minimum-spanning-tree#prim#kruskal#dijkstra#shortest-path#priority-queue#union-find#optimal-substructure

연결할 정점이 여럿일 때 비용을 가장 적게 들이는 방법, 한 정점에서 다른 정점까지 가장 싸게 가는 경로. 둘 다 최적화 문제(optimization problem) 다. 이런 문제를 푸는 한 가지 전략이 매 순간 가장 좋아 보이는 선택을 하는 그리디(greedy) 다. 그리디가 늘 통하지는 않지만, 어떤 문제는 그리디로 정확한 최적해가 나온다는 것이 증명되어 있다. 이 글은 그 대표 사례인 최소 신장 트리(MST)와 단일 출발점 최단 경로(Dijkstra)를 다룬다.

최적화 문제와 그리디

최적화 문제는 총비용을 최소화하거나 총이익을 최대화하는 문제다. 푸는 방식은 크게 둘로 갈린다.

모든 경우를 분석해 최선을 찾는다. 동적 계획법(DP)이 이 계열이다.
일련의 선택을 하되, 그 선택들의 전체 효과가 최적이 되도록 한다. 그리디가 이 계열이다.

그리디 알고리즘

그리디는 선택을 순차적으로 하되 다음 두 성질을 가진다.

각 선택이 그 시점에서 최선이다. 단, “단기(short-term)” 기준에 따른 최선이고, 그 기준은 평가 비용이 너무 크지 않아야 한다.
한 번 한 선택은 되돌릴 수 없다(cannot be undone). 나중에 그게 나쁜 선택이었음이 드러나도 무를 수 없다.

여기서 그리디의 약점이 나온다. 당장의 비용이 작은 행동이, 나중에 큰 비용을 피할 수 없는 상황으로 몰아넣을 수 있다. 그래서 그리디가 최적해를 보장하는지는 문제마다 따로 증명해야 한다.

다행히 일부 그래프 최적화 문제는 그리디로 정확하게(exactly) 풀린다.

모든 정점을 잇는 최소 비용 → 최소 신장 트리 알고리즘
두 정점 사이 최단 경로 → 단일 출발점 최단 경로 알고리즘

최소 신장 트리(MST)

연결된 무방향 그래프 $G = (V, E)$에 대해 신장 트리(spanning tree) 는 다음을 만족하는 $G$의 부분그래프다.

무방향 트리이고(사이클이 없고),
$G$의 모든 정점을 포함한다.

가중 그래프 $G = (V, E, W)$에서 부분그래프의 무게(weight) 는 그 안에 든 간선들의 가중치 합이다. 최소 신장 트리(minimum spanning tree) 는 무게가 최소인 신장 트리다.

주의할 점은 MST가 유일하지 않을 수 있다는 것이다. 같은 최소 무게를 갖는 신장 트리가 여러 개일 수 있다. 예를 들어 정점 $A, B, C, D$에 간선 $AB = 2$, $AC = 3$, $AD = 2$, $CD = 4$, $BD = 1$ 같은 그래프에서는 무게가 같은 신장 트리가 둘 이상 나온다.

MST를 구하는 그리디 알고리즘은 두 가지가 대표적이다. 정점을 키워 나가는 Prim과 간선을 골라 나가는 Kruskal이다.

Prim 알고리즘

Prim은 트리를 하나의 정점에서 시작해 간선을 하나씩 붙여 키운다.

임의의 시작 정점 하나를 고른다(루트 역할).
지금까지 만든 트리에서, 붙일 수 있는 모든 간선 중 가중치가 가장 작은 간선을 골라 트리에 붙이고, 그 간선에 딸린 정점을 트리에 추가한다. ← 이 선택이 그리디다.
모든 정점이 트리에 들어올 때까지 반복한다.

알고리즘이 도는 동안 정점은 서로 겹치지 않는 세 부류로 나뉜다.

상태	의미
tree	지금까지 만든 트리에 들어 있는 정점
fringe	트리에 없지만 트리의 어떤 정점과 인접한 정점(곧 트리가 될 후보)
unseen	그 외 전부(아직 살펴보지 않은 정점)

개요

PrimMST(G, n):
    모든 정점을 unseen으로 초기화
    임의의 정점 s를 골라 tree로 분류
    s에 인접한 모든 정점을 fringe로 분류
    while (fringe 정점이 있는 동안):              // 약 n-1번 반복
        tree 정점 t와 fringe 정점 v 사이에서
            가중치가 최소인 간선 tv를 고른다       // greedy
        v를 tree로 재분류하고, 간선 tv를 트리에 추가
        v에 인접한 unseen 정점들을 fringe로 재분류

매 반복마다 “fringe 중에서 트리에 가장 싸게 붙는 정점”을 하나 뽑는다. 이 “최솟값 뽑기”를 어떤 자료구조로 하느냐가 전체 복잡도를 결정한다.

우선순위 큐와 복잡도

fringe 정점들을 우선순위 큐(priority queue)에 넣고, 각 정점의 키(key)를 “트리에 붙는 최소 간선 가중치”로 둔다. 새 정점이 트리에 들어올 때마다 인접한 fringe 정점들의 키를 더 작은 값으로 갱신하는데, 이 연산이 decreaseKey다. 필요한 연산은 insert, removeMin, decreaseKey 세 가지이고, 구현마다 비용이 다르다.

연산	정렬 안 된 배열	정렬된 배열	힙(heap)
`insert`	$O(1)$	$O(n)$	$O(\log n)$
`removeMin`	$O(n)$	$O(1)$	$O(\log n)$
`decreaseKey`	$O(1)$	$O(n)$	$O(\log n)$

정렬 안 된 배열로 구현하면 매 반복의 removeMin이 $O(n)$이고 이를 $n-1$번 하므로, 초기화 $O(n)$까지 더해 전체가 다음과 같다.

\[O(n) + (n-1) \times O(n) = O(n^2)\]

이는 밀집 그래프($m \in O(n^2)$)에 유리하다. 반면 힙으로 구현하면 정점마다 removeMin($O(\log n)$)을 하고 간선마다 decreaseKey($O(\log n)$)를 하므로 다음과 같다.

\[O(n \log n + 2m \log n) = O(m \log n)\]

이는 희소 그래프($m \in O(n)$)에 유리하다. 즉 밀집 그래프면 정렬 안 된 배열($O(n^2)$), 희소 그래프면 힙($O(m \log n)$) 을 쓰는 것이 정석이다.

Kruskal 알고리즘

Kruskal은 정점이 아니라 간선 정보로 접근한다. 전체 간선을 가벼운 순서로 보면서, 사이클을 만들지 않는 간선만 골라 숲(forest)에 추가한다.

KruskalMST(G, n):
    R = E           // R은 남은 간선들
    F = ∅           // F는 숲(트리)을 이루는 간선들
    while (R이 비어 있지 않은 동안):              // F가 n-1개 간선이면 종료
        R에서 가장 가벼운(짧은) 간선 vw를 꺼낸다
        if (vw가 F에 사이클을 만들지 않으면):
            vw를 F에 추가
    return F

“가장 가벼운 간선 꺼내기”는 두 방식으로 구현한다.

간선을 미리 정렬해 두면 꺼내기가 $O(1)$. 정렬에 $O(m \log m)$.
우선순위 큐(최소 힙) 로 두면 꺼내기가 $O(\log m)$.

어느 쪽이든 전체 시간은 다음과 같다.

\[O(m \log m) \;\xrightarrow{\;m \in O(n^2)\;}\; O(2m \log n) = O(m \log n)\]

사이클 판정 — Union-Find

핵심은 “이 간선을 추가하면 사이클이 생기는가”를 빠르게 판정하는 것이다. Kruskal은 트리들의 숲을 유지하며, 서로 다른 트리를 잇는 간선만 받아들인다(같은 트리 안의 두 정점을 이으면 사이클이 된다).

이를 위해 서로소 집합(disjoint set)을 관리하는 자료구조가 필요하고, 두 연산을 제공한다.

find(u): $u$가 속한 집합(트리)을 반환한다.
union(u, v): $u$가 속한 집합과 $v$가 속한 집합을 하나로 합친다.

간선 $vw$를 볼 때 find(v)와 find(w)가 다르면(다른 트리면) 추가하고 union으로 합치며, 같으면 버린다. 이 자료구조가 Union-Find다.

단일 출발점 최단 경로

최단 경로 문제에는 입력에 따라 여러 변형이 있다.

변형	입력	의미
single-source	$(G, s)$	출발점 $s$에서 모든 정점까지
single-destination	$(G, t)$	모든 정점에서 도착점 $t$까지
single-pair	$(G, s, t)$	한 쌍 $s \to t$만
all-pair	$(G)$	모든 정점 쌍

흥미로운 사실은, 최악의 경우 한 쌍 $s \to t$ 최단 경로를 찾는 것이 $s$에서 도달 가능한 모든 정점까지의 최단 경로를 찾는 것보다 쉽지 않다는 점이다. $s \to t$만 구하려 해도 결국 $s$에서 출발하는 경로를 두루 키워야 $t$에 닿기 때문이다. 그래서 표준 문제를 단일 출발점 최단 경로(single-source shortest path) 로 잡는다.

최단 경로의 정의와 성질

가중 그래프 $G = (V, E, W)$에서 $k$개 간선 $xv_1, v_1v_2, \dots, v_{k-1}y$로 이루어진 비어 있지 않은 경로 $P$의 무게는 간선 가중치의 합이다.

\[W(P) = W(xv_1) + W(v_1v_2) + \cdots + W(v_{k-1}y)\]

$x = y$면 빈 경로를 $x$에서 $y$로 가는 경로로 보고 무게는 0이다. $x$와 $y$ 사이 어떤 경로도 $W(P)$보다 작은 무게를 갖지 않으면 $P$를 최단 경로(shortest path), 즉 최소 무게 경로라 한다. 최단 경로는 여럿일 수 있고, 하나만 찾으면 된다.

최단 경로 성질(최적 부분 구조). $x$에서 $z$로 가는 최단 경로가 “$x \to y$ 경로 $P$ 다음에 $y \to z$ 경로 $Q$”로 이루어진다고 하자. 그러면 $P$는 $x \to y$의 최단 경로이고 $Q$는 $y \to z$의 최단 경로다.

즉 최단 경로를 잘라 보면 각 조각도 최단 경로다. 이것이 최적 부분 구조(optimal substructure) 이며, 그리디와 DP가 동작하는 근거다. 단, 역은 성립하지 않는다. 최단 경로 조각들을 이어 붙인다고 전체가 최단 경로가 되지는 않는다.

Dijkstra 알고리즘

Dijkstra는 단일 출발점 최단 경로를 푸는 그리디 알고리즘이다. 전제 조건이 하나 있다.

모든 가중치가 음이 아니어야 한다(nonnegative weights).

구조는 Prim과 거의 같다. 정점을 tree / fringe / unseen으로 나누고 fringe에서 하나씩 트리로 끌어온다. 단, 고르는 기준이 다르다. Prim은 “트리에 붙는 간선 가중치”가 최소인 정점을 골랐지만, Dijkstra는 “출발점 $s$에서의 누적 거리“가 최소인 정점을 고른다.

dijkstraSSSP(G, n):
    모든 정점을 unseen으로 초기화
    출발 정점 s를 tree로 분류하고 d(s, s) = 0
    s에 인접한 모든 정점을 fringe로 분류
    while (fringe 정점이 있는 동안):
        tree 정점 t와 fringe 정점 v 사이에서
            d(s, t) + W(tv)가 최소가 되는 간선을 고른다    // greedy
        v를 tree로 재분류하고 간선 tv를 트리에 추가
        d(s, v) = d(s, t) + W(tv)
        v에 인접한 unseen 정점들을 fringe로 분류

Prim의 선택 기준 $W(tv)$가 Dijkstra에서는 $d(s, t) + W(tv)$로 바뀐 것이 전부다. 만들어지는 트리는 MST가 아니라 최단 경로 트리(shortest-path tree) 이고, 각 정점에 부모(predecessor)를 함께 기록하면 출발점에서 그 정점까지의 최단 경로를 역추적할 수 있다.

복잡도도 Prim과 동일한 구조다. 정렬 안 된 배열이면 $O(n^2)$, 힙이면 decreaseKey까지 포함해 $O(m \log n)$이다.

정당성

알고리즘의 핵심 정리(Theorem 8.6)는 이렇다.

가중치가 음이 아닌 가중 그래프 $G = (V, E, W)$에서 $V’ \subseteq V$, $s \in V’$라 하자. 각 $y \in V’$에 대해 $d(s, y)$가 $G$에서 $s \to y$의 최단 거리라고 가정한다. 한쪽 끝 $y$는 $V’$에, 다른 끝 $z$는 $V - V’$에 둔 모든 간선 중에서 $d(s, y) + W(yz)$를 최소화하는 간선 $yz$를 고르면, “$s \to y$ 최단 경로 다음에 간선 $yz$”는 $s \to z$의 최단 경로다.

이 정리가 매 반복에서 새로 트리에 넣는 정점의 거리가 확정적으로 최단임을 보장한다. 결국 Dijkstra는 음이 아닌 가중치의 방향 그래프에서 $s$로부터 도달 가능한 모든 정점까지의 최단 거리를 정확히 계산한다.

왜 음수 가중치에서 깨지는가

Dijkstra가 음수 가중치를 다루지 못하는 이유는 그리디 + “한 번 확정하면 무르지 않음” 때문이다. 다음 그래프를 보자.

      A (= s)
   2 /     \ 5
    B  ←——— C
       -10

간선은 $A \to B = 2$, $A \to C = 5$, $C \to B = -10$이다. Dijkstra는 $d(A, A) = 0$을 고정한 뒤 fringe에서 가장 가까운 $B$($d = 2$)를 먼저 확정한다. 하지만 실제 최단 경로는 $A \to C \to B = 5 + (-10) = -5$로 더 짧다. Dijkstra는 $B$를 이미 $d = 2$로 확정해 버렸기 때문에 나중에 등장하는 음수 간선 $C \to B$를 반영하지 못한다. 음수 간선이 있으면 “더 멀리 돌아가는 게 더 싸질” 수 있는데, 그리디는 그 가능성을 닫아 버린다. 이런 경우엔 Bellman-Ford 같은 다른 알고리즘이 필요하다.