원소들을 동적으로 그룹으로 묶고, 두 원소가 같은 그룹에 속하는지 묻는다 — 이것이 서로소 집합(disjoint set)이 푸는 전부다. 단순한 두 연산 find와 union에 경로 압축과 랭크 합치기라는 두 최적화를 더하면, 거의 모든 호출이 amortized 상수 시간에 끝난다. 이 페이지는 동치관계와 분할의 수학적 대응을 세우고, 그 위에서 거의-상수 복잡도를 증명한 뒤, Expert 문제가 이 구조를 어디에 쓰는지 추적한다.
n개의 원소가 있다. 처음에는 각자가 홀로 자기만의 그룹이다. 두 종류의 연산이 시간순으로 섞여 들어온다 — union(a, b): a가 속한 그룹과 b가 속한 그룹을 하나로 합친다. find(a): a가 속한 그룹의 대표(representative)를 반환한다. 두 원소가 같은 그룹인지는 find(a) == find(b)로 판정한다.
이 문제는 본질적으로 동치관계(equivalence relation)를 동적으로 유지하는 일이다. "같은 그룹에 속함"이라는 관계는 반사적(a ∼ a)·대칭적(a ∼ b ⇒ b ∼ a)·추이적(a ∼ b ∧ b ∼ c ⇒ a ∼ c)이다. 그리고 §2에서 보듯, 한 집합 위의 동치관계는 그 집합의 분할(partition) — 겹치지 않으면서 전체를 덮는 부분집합들의 모임 — 과 정확히 일대일로 대응한다. union은 분할의 두 조각을 잇고, find는 어느 조각인지 묻는다.
자료구조의 발상은 단순하다. 각 그룹을 뿌리 있는 트리(rooted tree)로 표현하고, 트리의 뿌리를 그 그룹의 대표로 삼는다. 각 원소는 부모 포인터 parent[] 하나만 가진다. find는 부모를 따라 뿌리까지 올라가고, union은 한 트리의 뿌리를 다른 트리의 뿌리에 매단다. 문제는 — 순진하게 매달면 트리가 일직선으로 길어져 find가 O(n)이 된다는 것이다. 그 함정을 §3의 두 최적화가 무너뜨린다.
Union-Find가 "올바르게" 그룹을 유지한다는 말의 의미를 먼저 못 박자. 그것은 자료구조가 언제나 어떤 분할을 정확히 표현하며, union·find가 그 분할 위의 정직한 연산이라는 뜻이다.
집합 S 위의 동치관계들과 S의 분할들 사이에는 자연스러운 일대일 대응이 존재한다. 동치관계 ∼가 주어지면 동치류(equivalence class) [x] = { y : y ∼ x }들의 모임이 분할을 이루고, 거꾸로 분할 𝒫가 주어지면 "같은 조각에 속함"이 동치관계를 이룬다.
덮음(covering). 반사성에 의해 모든 x는 x ∼ x이므로 x ∈ [x]. 따라서 동치류들의 합집합이 S 전체다.
서로소(disjointness). 두 동치류 [x]와 [y]가 공통 원소 z를 가진다 하자. 그러면 z ∼ x이고 z ∼ y. 대칭성으로 x ∼ z, 추이성으로 x ∼ y. 임의의 w ∈ [x]에 대해 w ∼ x ∼ y이므로 w ∈ [y] — 즉 [x] ⊆ [y]. 대칭으로 [y] ⊆ [x]. 따라서 두 동치류는 같거나(공통 원소가 있으면) 완전히 서로소다.
덮음과 서로소가 곧 분할의 정의다. 역방향("같은 조각에 속함"이 반사·대칭·추이를 만족)은 분할의 정의에서 즉시 따라온다.
union(a, b)는 동치관계에 "a ∼ b"라는 사실을 하나 추가하는 연산이다. 그 결과의 동치관계는 — "기존 관계와 a ∼ b를 모두 담는 가장 작은 동치관계", 즉 추이 폐포(transitive closure)다. 분할의 언어로는, a를 품은 조각과 b를 품은 조각을 합집합으로 잇고 나머지 조각은 그대로 둔 새 분할이다. 두 조각이 이미 같았다면 분할은 변하지 않는다. 따라서 union 연산열은 분할을 점점 거칠게(coarser) 만들어 가며, 동치류의 개수는 단조 비증가다.
두 최적화가 트리를 납작하게 유지한다. union by rank: 두 트리를 합칠 때 "더 낮은 트리를 더 높은 트리 밑에" 매단다 — 그래야 합쳐진 트리의 높이가 불필요하게 자라지 않는다(rank는 트리 높이의 상한 추정치다). 경로 압축(path compression): find가 뿌리를 찾고 돌아오는 길에, 사슬에 있던 모든 노드의 부모를 뿌리로 직접 다시 매단다 — 다음번 find는 한 걸음에 끝난다.
#include <vector>#include <numeric>using namespace std;struct DSU { vector<int> parent, rnk, sz; int groups; // 현재 동치류 개수 DSU(int n) : parent(n), rnk(n, 0), sz(n, 1), groups(n) { iota(parent.begin(), parent.end(), 0); // parent[i]=i } // 경로 압축 — 사슬 전체를 뿌리에 직결 int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; // path halving x = parent[x]; } return x; } // union by rank — 낮은 트리를 높은 트리 밑에 bool unite(int a, int b) { a = find(a); b = find(b); if (a == b) return false; // 이미 같은 그룹 if (rnk[a] < rnk[b]) swap(a, b); parent[b] = a; sz[a] += sz[b]; if (rnk[a] == rnk[b]) ++rnk[a]; // 동률일 때만 +1 --groups; return true; } bool same(int a, int b) { return find(a) == find(b); } int size(int x) { return sz[find(x)]; }};
parent[x] = parent[parent[x]]는 path halving — 사슬을 따라 오르며 한 칸 건너뛰기로 부모를 손자(=조부모)로 바꾼다. 재귀로 사슬 전체를 뿌리에 직결하는 완전 압축과 점근 복잡도가 같으면서 스택을 쓰지 않아 더 안전하다. 라인 25의 swap은 union by rank의 본체 — 항상 a가 더 높은(혹은 같은) 트리가 되도록 맞춘 뒤 b를 a 밑에 매단다. 라인 28에서 rank는 두 트리의 높이가 같을 때만 1 증가한다 — 다를 때는 낮은 쪽이 흡수되어 전체 높이가 그대로이기 때문이다. sz[]와 groups는 "각 그룹 크기"·"그룹 개수"를 묻는 문제를 위한 부수 정보로, 핵심 정확성에는 관여하지 않는다.
union by rank만 쓰면 트리 높이가 O(log n)으로 묶여, 각 연산이 O(log n)이다(rank가 r인 트리는 적어도 2ʳ개의 노드를 품으므로 r ≤ log₂ n). 여기에 경로 압축을 더하면 — Tarjan의 고전적 분석에 의해 — m번의 연산이 총 O(m · α(n))에 끝난다. α는 역 아커만 함수(inverse Ackermann)로, 우주의 원자 수보다 큰 n에 대해서도 α(n) ≤ 5다. 실전에서 Union-Find는 사실상 상수 시간 자료구조로 취급해도 무방하다. 공간은 parent·rank·size 배열로 O(n).
union(0,1), union(1,2), …을 호출하는 적대적 패턴이 정확히 이 함정을 판다. α(n)의 마법은 두 최적화의 곱으로만 나온다 — 어느 하나도 생략하지 말 것.
Expert 문제에서 Union-Find는 "두 원소를 같은 그룹으로 묶어라"라는 직설적 형태로 오기보다, 문제의 어떤 관계가 동치관계임을 알아차리는 통찰을 요구하는 형태로 등장한다. 관계가 추이적이라는 것만 보이면, 그 다음은 표준 DSU다.
IoT가전의 핵심은, 장치들 사이의 "같은 방에 속한다"는 관계가 반사·대칭·추이를 모두 만족하는 동치관계임을 인식하는 것이다. "장치 A와 B가 같은 방", "B와 C가 같은 방"이라는 정보가 시간순으로 들어오면, 추이성에 의해 A와 C도 같은 방이다 — 바로 union 연산이다. 어느 두 장치가 함께 제어되어야 하는지(같은 방인지) 묻는 질의는 find 비교 한 번이다. 방 개수는 groups 변수가, 각 방의 장치 수는 sz[]가 즉시 답한다. 문제의 본질을 "동적 분할 유지"로 번역하는 순간, 구현 난이도는 §3의 30줄로 떨어진다.
간선을 하나씩 추가하며 "이 간선이 사이클을 만드는가?"를 묻는 문제에서, Union-Find는 즉답을 준다 — 간선 (u,v)의 두 끝점이 이미 같은 그룹(find(u)==find(v))이면 그 간선은 사이클을 닫는다. 이것이 Kruskal MST의 엔진이다 — 간선을 가중치 오름차순으로 정렬(그리디 교환논법으로 정당화되는 cut property)하고, 사이클을 만들지 않는 간선만 unite로 받아들인다. unite가 false를 반환하면 그 간선은 버려진다.
Union-Find는 합치기만 할 뿐 쪼개기(split)를 지원하지 않는다 — 트리에서 노드를 떼어내려면 자손 전체를 갱신해야 하기 때문이다. 그래서 "연결을 끊는" 질의가 섞인 문제는, 모든 질의를 미리 읽어(offline) 시간을 거꾸로 처리한다 — 삭제를 시간 역순의 추가로 바꿔 union만으로 처리하는 고전적 트릭이다. 온라인으로 분리까지 필요하면 link-cut tree 같은 더 무거운 구조로 넘어가야 한다.
| 구조 | union/find | 분리 지원 | 쓰임 |
|---|---|---|---|
| Union-Find (DSU) | O(α(n)) | 불가 | 동적 분할·MST·사이클 검출 — 가장 흔한 선택 |
| DFS/BFS 라벨링 | O(V+E) 1회 | 정적 | 그래프가 고정 — 한 번에 연결 성분 라벨링 |
| Link-Cut Tree | O(log n) | 가능 | 간선 추가·삭제가 모두 온라인으로 섞일 때 |
| Euler Tour Tree | O(log n) | 가능 | 동적 연결성 + 부분트리 집계 질의 |
| 가중 Union-Find | O(α(n)) | 불가 | 대표까지의 상대 거리/패리티를 함께 유지 |
그래프가 처음부터 고정되어 있고 한 번만 연결 성분을 알면 된다면 DFS/BFS 한 번이면 충분하다 — Union-Find의 진가는 간선이 시간순으로 추가되며 그 사이사이에 연결 질의가 끼어드는 동적 상황이다. 추가와 삭제가 둘 다 온라인으로 섞이면 link-cut tree나 Euler tour tree로 올라가야 하지만, 그 대가는 O(α(n))에서 O(log n)으로의 상수·차수 모두의 손해와 구현 복잡도의 폭증이다. 가중 Union-Find는 같은 골격에 "대표까지의 거리/패리티" 정보를 부모 간선에 실어, "두 원소의 상대 관계"를 묻는 문제로 확장한다. 그리고 Kruskal MST의 정당성은 그리디 교환논법의 cut property에서 온다 — 두 원리는 한 알고리즘의 두 절반이다.