최소 신장 트리와 유니온 파인드

MST(최소 신장 트리)는 모든 정점을 가장 적은 비용으로 연결하는 문제입니다. 중요한 점은 가장 싼 간선만 고르는 것이 아니라, 사이클 없이 연결을 유지하는 것입니다. 그래서 Kruskal(간선 정렬)과 DSU(사이클 판정)를 같이 사용합니다.

정렬까지만 구현하고 사이클 처리를 빼먹는 실수가 자주 나옵니다. 여기서는 간선 선택과 사이클 검사를 역할별로 분리해 구현 흐름이 흔들리지 않게 구성했습니다. 코테 실전에서도 그대로 재사용할 수 있는 형태로 설명합니다.

핵심 원리 프레임: MST·유니온 파인드

MST는 간선 선택 관점과 사이클 검사 도구를 분리해서 보면 구현이 훨씬 단순해집니다. 코드 전에 어떤 간선을 채택할지를 우선 문장으로 적어 두세요.

최소 신장 트리(MST)는 모든 정점을 연결하면서 비용 합을 최소로 만든 간선 집합입니다. 연결 무방향 가중 그래프에서 사이클 없이 V-1개의 간선으로 전체를 잇는 최소 비용 부분 그래프를 뜻합니다. 정점이 5개라면 간선 4개만 선택해 전체를 연결하면서 총 비용을 가장 작게 만들어야 합니다.

Kruskal은 간선을 값이 작은 순서로 보며 안전한 간선만 선택하는 알고리즘입니다. 가중치 오름차순 정렬 후, 간선이 서로 다른 컴포넌트를 잇는 경우에만 채택합니다. 1-2(1), 2-3(2), 1-3(3)라면 마지막 간선은 사이클을 만들기 때문에 제외됩니다.

DSU(Union-Find)는 두 정점이 같은 컴포넌트인지 빠르게 확인하는 자료구조입니다. 경로 압축과 union-by-size/rank를 쓰면 find/union을 거의 상수 시간에 처리할 수 있습니다. find(u)==find(v)이면 이미 연결된 상태이므로 해당 간선을 추가하면 사이클이 생긴다는 뜻입니다.

MST 선택이 운영 비용에 미치는 영향

네트워크 설계, 도로 연결, 배선 비용 최소화 등에서 MST 패턴이 반복됩니다.
간선 수가 큰 그래프에서는 사이클 판정을 효율적으로 하지 않으면 성능이 급격히 떨어집니다.

DSU를 결합하면 판정 비용을 크게 줄일 수 있어 대규모 입력에서도 안정적입니다.

DSU 동작 디버깅 시나리오

여기서는 오답 -> 디버깅 -> 교정 -> 검증 흐름으로 추적해, 어디서 불변식이 깨지는지 단계별로 확인합니다.

Kruskal + DSU 흐름을 작은 예제로 따라가 봅니다.

간선(가중치 오름차순): (1-2,1), (2-3,2), (1-3,3)

1-2를 추가합니다.
2-3를 추가합니다.
1-3은 이미 같은 컴포넌트라 사이클이 되어 제외합니다.
채택 간선 수가 N-1이면 MST가 완성됩니다.

MST/DSU: DSU 기본 구현

문제 의도: 사이클 판정의 핵심인 DSU(find/union) 동작을 확인합니다.
입력 예시: union(1,2), union(2,3), union(1,3)
출력 예시: true, true, false

main.cpp

#include <iostream>
#include <vector>
using namespace std;

struct DSU {
    vector<int> parent, sz;
    DSU(int n) : parent(n + 1), sz(n + 1, 1) {
        for (int i = 0; i <= n; ++i) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (sz[ra] < sz[rb]) swap(ra, rb);
        parent[rb] = ra;
        sz[ra] += sz[rb];
        return true;
    }
};

int main() {
    DSU d(5);
    cout << d.unite(1, 2) << "\n";
    cout << d.unite(2, 3) << "\n";
    cout << d.unite(1, 3) << "\n";
    return 0;
}

Main.java

public class Main {
    static class DSU {
        int[] parent;
        int[] size;

        DSU(int n) {
            parent = new int[n + 1];
            size = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }

        boolean union(int a, int b) {
            int ra = find(a), rb = find(b);
            if (ra == rb) return false;
            if (size[ra] < size[rb]) {
                int t = ra; ra = rb; rb = t;
            }
            parent[rb] = ra;
            size[ra] += size[rb];
            return true;
        }
    }

    public static void main(String[] args) {
        DSU d = new DSU(5);
        System.out.println(d.union(1, 2));
        System.out.println(d.union(2, 3));
        System.out.println(d.union(1, 3));
    }
}

main.py

class DSU:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.size = [1] * (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, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False

        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra

        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

d = DSU(5)
print(d.union(1, 2))  # True
print(d.union(2, 3))  # True
print(d.union(1, 3))  # False (cycle)

main.rs

#[derive(Debug)]
struct Dsu {
    parent: Vec<usize>,
    size: Vec<usize>,
}

impl Dsu {
    fn new(n: usize) -> Self {
        let mut parent = Vec::new();
        for i in 0..=n {
            parent.push(i);
        }
        Self {
            parent,
            size: vec![1; n + 1],
        }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            let root = self.find(self.parent[x]);
            self.parent[x] = root;
        }
        self.parent[x]
    }

    fn union(&mut self, a: usize, b: usize) -> bool {
        let mut ra = self.find(a);
        let mut rb = self.find(b);
        if ra == rb {
            return false;
        }
        if self.size[ra] < self.size[rb] {
            std::mem::swap(&mut ra, &mut rb);
        }
        self.parent[rb] = ra;
        self.size[ra] += self.size[rb];
        true
    }
}

fn main() {
    let mut d = Dsu::new(5);
    println!("{}", d.union(1, 2));
    println!("{}", d.union(2, 3));
    println!("{}", d.union(1, 3));
}

MST/유니온파인드 동작 초기 거리값 검토

union이 실패(False)하면 같은 컴포넌트라는 의미이며, 간선을 추가하면 사이클이 생깁니다.
경로 압축과 union-by-size를 쓰면 연산이 거의 상수 시간으로 동작합니다.
MST뿐 아니라 연결성 검사 문제에도 재사용됩니다.

평균 시간복잡도: find/union 1회당 거의 O(1) (아커만 역함수 수준)
공간복잡도: O(V)

MST/DSU: Kruskal MST

문제 의도: 간선 정렬 + DSU 조합으로 MST 총 가중치를 계산합니다.
입력 예시: 가중치 간선 목록
출력 예시: MST 총 가중치 또는 불가능 시 None/-1

main.cpp

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n + 1), sz(n + 1, 1) {
        for (int i = 0; i <= n; ++i) p[i] = i;
    }
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (sz[ra] < sz[rb]) swap(ra, rb);
        p[rb] = ra;
        sz[ra] += sz[rb];
        return true;
    }
};

int kruskal(int n, vector<tuple<int, int, int>> edges) {
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    int total = 0, used = 0;
    for (const auto& edge : edges) {
        int w = get<0>(edge);
        int u = get<1>(edge);
        int v = get<2>(edge);
        if (dsu.unite(u, v)) {
            total += w;
            used++;
            if (used == n - 1) break;
        }
    }
    if (used != n - 1) return -1;
    return total;
}

int main() {
    vector<tuple<int, int, int>> edges = {{1,1,2}, {3,1,3}, {2,2,3}, {4,2,4}, {5,3,4}};
    cout << kruskal(4, edges) << "\n";
    return 0;
}

Main.java

import java.util.*;

public class Main {
    static class DSU {
        int[] p, sz;
        DSU(int n) {
            p = new int[n + 1];
            sz = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                p[i] = i;
                sz[i] = 1;
            }
        }
        int find(int x) {
            if (p[x] != x) p[x] = find(p[x]);
            return p[x];
        }
        boolean union(int a, int b) {
            int ra = find(a), rb = find(b);
            if (ra == rb) return false;
            if (sz[ra] < sz[rb]) {
                int t = ra; ra = rb; rb = t;
            }
            p[rb] = ra;
            sz[ra] += sz[rb];
            return true;
        }
    }

    static Integer kruskal(int n, int[][] edges) {
        Arrays.sort(
            edges,
            new Comparator<int[]>() {
                @Override
                public int compare(int[] a, int[] b) {
                    return Integer.compare(a[0], b[0]);
                }
            }
        );
        DSU dsu = new DSU(n);
        int total = 0, used = 0;
        for (int[] e : edges) {
            int w = e[0], u = e[1], v = e[2];
            if (dsu.union(u, v)) {
                total += w;
                used++;
                if (used == n - 1) break;
            }
        }
        return used == n - 1 ? total : null;
    }

    public static void main(String[] args) {
        int[][] edges = {{1,1,2},{3,1,3},{2,2,3},{4,2,4},{5,3,4}};
        System.out.println(kruskal(4, edges));
    }
}

main.py

class DSU:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.size = [1] * (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, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

def kruskal(n, edges):
    dsu = DSU(n)
    total = 0
    used = 0

    edges_sorted = edges[:]
    edges_sorted.sort()
    for w, u, v in edges_sorted:
        if dsu.union(u, v):
            total += w
            used += 1
            if used == n - 1:
                break

    if used != n - 1:
        return None  # 연결 그래프 아님
    return total

edges = [
    (1, 1, 2),
    (3, 1, 3),
    (2, 2, 3),
    (4, 2, 4),
    (5, 3, 4)
]
print(kruskal(4, edges))  # 7

main.rs

#[derive(Debug)]
struct Dsu {
    parent: Vec<usize>,
    size: Vec<usize>,
}

impl Dsu {
    fn new(n: usize) -> Self {
        let mut parent = Vec::new();
        for i in 0..=n {
            parent.push(i);
        }
        Self {
            parent,
            size: vec![1; n + 1],
        }
    }
    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            let root = self.find(self.parent[x]);
            self.parent[x] = root;
        }
        self.parent[x]
    }
    fn union(&mut self, a: usize, b: usize) -> bool {
        let mut ra = self.find(a);
        let mut rb = self.find(b);
        if ra == rb {
            return false;
        }
        if self.size[ra] < self.size[rb] {
            std::mem::swap(&mut ra, &mut rb);
        }
        self.parent[rb] = ra;
        self.size[ra] += self.size[rb];
        true
    }
}

fn kruskal(n: usize, edges: &mut Vec<(i32, usize, usize)>) -> Option<i32> {
    edges.sort_by_key(|e| e.0);
    let mut dsu = Dsu::new(n);
    let mut total = 0;
    let mut used = 0;
    for &(w, u, v) in &*edges {
        if dsu.union(u, v) {
            total += w;
            used += 1;
            if used == n - 1 {
                break;
            }
        }
    }
    if used == n - 1 { Some(total) } else { None }
}

fn main() {
    let mut edges = vec![(1,1,2), (3,1,3), (2,2,3), (4,2,4), (5,3,4)];
    println!("{:?}", kruskal(4, &mut edges));
}

MST/유니온파인드 동작 완화 단계 추적

간선을 정렬한 뒤 순서대로 보되, union 성공 간선만 채택합니다.
정점 수 N에서 N-1개 간선이 채워지면 MST가 완성됩니다.
연결 그래프가 아니면 MST가 아니라 최소 신장 포레스트가 됩니다.

평균 시간복잡도: O(E log E)
최악 시간복잡도: O(E log E)
공간복잡도: O(V)

MST/DSU: Prim 알고리즘 비교

문제 의도: Prim으로 같은 MST 문제를 풀어 Kruskal과 선택 관점을 비교합니다.
입력 예시: 동일 그래프 간선 목록
출력 예시: Prim MST 총 가중치

main.cpp

#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

int prim(int n, const vector<tuple<int, int, int>>& edges) {
    vector<vector<pair<int, int>>> g(n + 1);
    for (const auto& edge : edges) {
        int w = get<0>(edge);
        int u = get<1>(edge);
        int v = get<2>(edge);
        g[u].push_back({w, v});
        g[v].push_back({w, u});
    }

    unordered_set<int> visited = {1};
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (auto item : g[1]) pq.push(item);

    int total = 0, used = 0;
    while (!pq.empty() && used < n - 1) {
        pair<int, int> cur = pq.top();
        pq.pop();
        int w = cur.first;
        int v = cur.second;
        if (visited.count(v)) continue;
        visited.insert(v);
        total += w;
        used++;
        for (auto nxt : g[v]) {
            if (!visited.count(nxt.second)) pq.push(nxt);
        }
    }
    return used == n - 1 ? total : -1;
}

int main() {
    vector<tuple<int, int, int>> edges = {{1,1,2},{3,1,3},{2,2,3},{4,2,4},{5,3,4}};
    cout << prim(4, edges) << "\n";
    return 0;
}

Main.java

import java.util.*;

public class Main {
    static Integer prim(int n, int[][] edges) {
        List<List<int[]>> g = new ArrayList<>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) {
            int w = e[0], u = e[1], v = e[2];
            g.get(u).add(new int[]{w, v});
            g.get(v).add(new int[]{w, u});
        }

        Set<Integer> visited = new HashSet<>();
        visited.add(1);
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            new Comparator<int[]>() {
                @Override
                public int compare(int[] a, int[] b) {
                    return Integer.compare(a[0], b[0]);
                }
            }
        );
        pq.addAll(g.get(1));

        int total = 0, used = 0;
        while (!pq.isEmpty() && used < n - 1) {
            int[] cur = pq.poll();
            int w = cur[0], v = cur[1];
            if (visited.contains(v)) continue;
            visited.add(v);
            total += w;
            used++;
            for (int[] nxt : g.get(v)) {
                if (!visited.contains(nxt[1])) pq.offer(nxt);
            }
        }
        return used == n - 1 ? total : null;
    }

    public static void main(String[] args) {
        int[][] edges = {{1,1,2},{3,1,3},{2,2,3},{4,2,4},{5,3,4}};
        System.out.println(prim(4, edges));
    }
}

main.py

import heapq
from collections import defaultdict

def prim(n, edges):
    g = defaultdict(list)
    for w, u, v in edges:
        g[u].append((w, v))
        g[v].append((w, u))

    visited = set([1])
    pq = []
    for item in g[1]:
        heapq.heappush(pq, item)

    total = 0
    used = 0
    while pq and used < n - 1:
        w, v = heapq.heappop(pq)
        if v in visited:
            continue
        visited.add(v)
        total += w
        used += 1
        for nxt in g[v]:
            if nxt[1] not in visited:
                heapq.heappush(pq, nxt)

    return total if used == n - 1 else None

edges = [
    (1, 1, 2),
    (3, 1, 3),
    (2, 2, 3),
    (4, 2, 4),
    (5, 3, 4)
]
print(prim(4, edges))  # 7

main.rs

use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashSet};

fn prim(n: usize, edges: &[(i32, usize, usize)]) -> Option<i32> {
    let mut g = vec![Vec::<(i32, usize)>::new(); n + 1];
    for &(w, u, v) in edges {
        g[u].push((w, v));
        g[v].push((w, u));
    }

    let mut visited = HashSet::new();
    visited.insert(1usize);
    let mut pq = BinaryHeap::<Reverse<(i32, usize)>>::new();
    for &item in &g[1] {
        pq.push(Reverse(item));
    }

    let mut total = 0;
    let mut used = 0usize;
    while let Some(Reverse((w, v))) = pq.pop() {
        if used == n - 1 {
            break;
        }
        if visited.contains(&v) {
            continue;
        }
        visited.insert(v);
        total += w;
        used += 1;
        for &nxt in &g[v] {
            if !visited.contains(&nxt.1) {
                pq.push(Reverse(nxt));
            }
        }
    }

    if used == n - 1 { Some(total) } else { None }
}

fn main() {
    let edges = vec![(1,1,2), (3,1,3), (2,2,3), (4,2,4), (5,3,4)];
    println!("{:?}", prim(4, &edges));
}