최소 신장 트리

어떤 문제를 푸는가

가중치 무방향 연결 그래프에서, 모든 정점을 연결하면서 간선 가중치 합이 최소
인 트리를 찾습니다. 도시들을 가장 싸게 도로로 잇기, 네트워크 최소 비용 연결
등이 전형적인 예입니다. 정점이 \(V\)개면 트리는 정확히 \(V-1\)개의 간선을 갖습니다.

두 가지 핵심 성질

MST 알고리즘의 정당성은 두 성질에서 나옵니다.

컷 성질 (Cut Property)

정점을 두 그룹으로 나눈 임의의 컷 에서, 그 컷을 가로지르는 간선 중 가장
가벼운 간선 은 어떤 MST에 반드시 포함됩니다.

직관: 그 가벼운 간선을 MST가 안 쓴다면, 컷을 가로지르는 다른(더 무거운)
간선을 쓰고 있어야 합니다. 그 무거운 간선을 빼고 가벼운 간선으로 바꾸면 여전히
트리이면서 비용이 줄어드니, 원래 것이 최소가 아니었다는 모순입니다.

사이클 성질 (Cycle Property)

어떤 사이클에서 가장 무거운 간선 은 어떤 MST에도 포함되지 않습니다.

이 두 성질이 그리디(가벼운 간선부터 채택)가 옳음을 보장합니다.

두 가지 표준 알고리즘

크루스칼의 아이디어

간선을 가중치 오름차순으로 정렬하고, 가벼운 것부터 본다. 그 간선의 두 끝점이
아직 다른 그룹 이면(유니온 파인드로 확인) 채택하고 합친다. 같은 그룹이면
추가 시 사이클이 생기므로 버린다. 이는 컷 성질의 직접적 적용입니다.

프림의 아이디어

한 정점에서 시작해 트리를 키운다. 매번 트리와 트리 밖을 잇는 가장 가벼운
간선 을 골라 새 정점을 흡수한다(우선순위 큐로 관리). 다익스트라와 형제처럼
닮았지만, 거리가 아니라 "트리까지의 간선 가중치"를 기준으로 삼습니다.

복잡도 정리

• 크루스칼: 정렬 \(O(E \log E)\)가 지배. DSU는 거의 상수.
• 프림(힙): \(O(E \log V)\).

대부분의 경우 구현이 단순한 크루스칼을 기본으로 씁니다. 다음 강의에서 두
구현과 응용을 봅니다.

크루스칼 구현 (C++)

유니온 파인드와 결합합니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct DSU {
    vector<int> p, s;
    DSU(int n) : p(n), s(n, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (s[a] < s[b]) swap(a, b);
        p[b] = a; s[a] += s[b];
        return true;
    }
};

int main() {
    int n, m; cin >> n >> m;
    vector<array<ll, 3>> e(m);            // {가중치, u, v}
    for (auto& x : e) cin >> x[1] >> x[2] >> x[0];
    sort(e.begin(), e.end());             // 가중치 오름차순

    DSU dsu(n + 1);
    ll cost = 0; int cnt = 0;
    for (auto& [w, u, v] : e) {
        if (dsu.unite(u, v)) {            // 사이클 안 생기면 채택
            cost += w;
            if (++cnt == n - 1) break;    // 간선 V-1개면 완성
        }
    }
    cout << (cnt == n - 1 ? cost : -1) << '\n';  // 연결 불가면 -1
}

cnt == n - 1로 끝나면 MST 완성, 못 채우면 그래프가 연결되지 않은 것입니다.

프림 구현 (C++, 힙)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, m; cin >> n >> m;
    vector<vector<pair<int, ll>>> adj(n + 1);   // (이웃, 가중치)
    for (int i = 0; i < m; i++) {
        int u, v; ll w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});               // 무방향
    }

    vector<char> in(n + 1, 0);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    pq.push({0, 1});                            // 정점 1에서 시작
    ll cost = 0; int cnt = 0;
    while (!pq.empty()) {
        auto [w, u] = pq.top(); pq.pop();
        if (in[u]) continue;                    // 이미 트리에 있음
        in[u] = 1; cost += w; cnt++;
        for (auto [v, ww] : adj[u])
            if (!in[v]) pq.push({ww, v});
    }
    cout << (cnt == n ? cost : -1) << '\n';
}

다익스트라와 코드가 거의 같지만, 큐에 넣는 값이 "시작점까지의 누적 거리"가
아니라 "이 간선 하나의 가중치"라는 점만 다릅니다.

흔한 함정

• 무방향 간선 양방향 등록 — 프림에서 양쪽을 다 넣어야 합니다.
• 연결성 미확인 — 채택한 간선이 \(V-1\)개가 안 되면 MST가 없습니다(비연결).
• 정렬 키 — 크루스칼에서 가중치를 맨 앞에 두어 가중치 기준 정렬.
• long long — 가중치 합이 클 수 있습니다.

응용 패턴

• 두 번째로 작은 신장 트리 — MST의 각 간선을 하나씩 제외하고 재계산하거나,
  사이클 성질을 이용.
• 최소 병목 신장 트리 — 가장 무거운 간선을 최소화 → MST가 그 답을 줍니다.
• 부분 연결만 필요(슈타이너 비슷) — 일부 정점만 잇기는 일반적으로 어렵지만,
  특수 케이스는 MST 변형으로.
• 오프라인 "어떤 가중치 이하 간선만 쓰면 연결되나" — 크루스칼 진행을 그대로
  활용(크루스칼 재구성 트리로 확장).

컷 성질이라는 단단한 토대 위에서 "가벼운 간선부터"라는 그리디가 통한다는 점이
이 단원의 핵심입니다.

출제 신호

MST는 문구가 비교적 정직한 편입니다.

• "모든 도시(컴퓨터, 섬)를 연결하는 최소 비용" — 가장 전형적인 문장
• "전선/도로/다리를 깔되 총 비용을 최소로", "유지할 간선만 남기고 나머지는 철거"
• 살짝 변장한 형태: "비용이 가장 비싼 간선을 최소화하며 연결"
  (MST의 간선 최댓값이 답 — MST는 최소 병목 신장 트리이기도 합니다)
• 정점이 좌표로 주어지고 "거리 비용으로 모두 연결" — 간선을 직접 만들어야 하는 형태

규모 신호는 \(E \le 10^5{\sim}10^6\)에 정렬 \(O(E \log E)\)가 통하는 크기입니다.
좌표 \(N\)개로 완전 그래프를 만들면 간선이 \(N^2/2\)개가 되니, \(N \le 2000\)
정도까지만 완전 그래프가 가능하다는 것도 같이 기억해 두세요.

풀이 결정 절차

1. "전부 연결 + 비용 최소"인지 확인합니다. 특정 두 점만 이으면 최단 경로 문제입니다.
2. 간선 리스트가 주어지는가, 직접 생성해야 하는가(좌표 거리 등)를 판단합니다.
3. 크루스칼(간선 정렬 + 유니온 파인드)을 기본으로 잡습니다. 조밀 그래프
   (\(E \approx V^2\))면 프림 \(O(V^2)\)가 메모리·시간에서 유리할 수 있습니다.
4. 연결이 보장되는지 확인합니다 — 보장이 없으면 "불가능" 출력 분기가 필요합니다.
5. 비용 합의 최대값을 추정해 long long 여부를 정합니다.

자주 하는 실수

• 간선 수 검증 누락 — 크루스칼이 끝났을 때 채택한 간선이 \(V-1\)개가 아니면
  그래프가 애초에 연결돼 있지 않은 것입니다. 합만 출력하면 오답.

sort(edges.begin(), edges.end());          // (w, u, v) 가중치순
long long total = 0; int used = 0;
for (auto [w, u, v] : edges) {
    if (find(u) == find(v)) continue;      // 사이클 — 버린다
    unite(u, v);
    total += w; used++;
}
if (used != n - 1) cout << -1 << '\n';     // 연결 불가 판정을 잊지 말 것
else cout << total << '\n';

• 유니온 파인드 최적화 누락 — 경로 압축 없는 DSU로 \(10^6\) 간선을 돌리면
  정렬보다 DSU에서 시간이 터집니다.
• 비용 합 오버플로 — 간선 \(10^5\)개 \(\times\) 가중치 \(10^6\)이면 이미 int 초과.
• "최대 비용 간선 최소화" 문제에서 합을 출력 — 병목 변형은 답이 합이 아니라
  채택한 간선 중 최댓값입니다. 문제의 목적 함수를 다시 읽으세요.
• 프림에서 다익스트라 습관 — 프림의 키는 "시작점부터의 거리"가 아니라
  "트리까지의 간선 한 개 비용"입니다. dist[v] = w 갱신을
  dist[v] = dist[u] + w로 쓰면 MST가 아니라 최단 경로 트리가 됩니다.

연습 방법

사이드바 연습 목록의 표준 MST 문제로 크루스칼 + DSU 템플릿을 굳히고,
이어서 (1) 좌표에서 간선을 생성하는 문제, (2) 병목(최댓값 최소화) 변형,
(3) "이미 깔린 간선이 일부 있는" 변형(해당 간선을 비용 0으로 먼저 union)
순서로 푸세요. 제출 전 점검 — 간선 \(V-1\)개 확인, long long, DSU 압축 —
세 줄 루틴이면 충분합니다. 태그된 문제 3문제 이상 해결 시 마스터 처리되어
레이팅 CLASS 보너스에 반영됩니다.