유니온 파인드란?
유니온 파인드(Union-Find), 또는 서로소 집합(Disjoint Set)은 여러 원소가 어느 그룹에 속하는지 관리하고, 두 그룹을 합치거나 두 원소가 같은 그룹인지 빠르게 답하는 자료구조입니다. 그래프 연결성 판정, 크루스칼 MST, 사이클 검출, 네트워크 묶음 등에 쓰입니다.
핵심 한 줄: "각 그룹을 대표(루트) 하나로 식별한다." 두 원소의 대표가 같으면 같은 그룹입니다.
두 가지 연산
- •find(x): x가 속한 그룹의 대표(루트)를 반환합니다. 부모를 따라 위로 올라가면 루트가 나옵니다.
- •union(a, b): a와 b의 두 대표를 찾아 한쪽을 다른 쪽 밑에 매달아 그룹을 합칩니다.
각 원소는 parent[] 배열로 자기 부모를 가리키고, 부모가 자기 자신이면 그게 루트입니다.
핵심은 두 가지 최적화
소박하게 구현하면 트리가 한 줄로 길어져 find가 O(n)이 됩니다. 두 최적화가 이를 거의 O(1)로 만듭니다.
- •경로 압축(path compression): find를 하며 지나간 노드들을 곧장 루트에 연결합니다. 다음 find가 즉시 끝납니다.
- •랭크/크기 기준 합치기(union by rank/size): 항상 작은(낮은) 트리를 큰 트리 밑에 붙여 높이가 늘지 않게 합니다.
둘을 함께 쓰면 한 연산의 평균 비용이 역 아커만 함수 α(n)에 비례 — 사실상 상수입니다.
동작 원리
1단계. 초기화: parent[i] = i (모두 자기 자신이 대표인 1인 그룹).
2단계. find(x): parent[x] != x인 동안 위로 올라가 루트를 찾고, 경로의 노드들을 루트에 직접 연결합니다.
3단계. union(a, b): ra = find(a), rb = find(b). 둘이 다르면 랭크가 작은 쪽을 큰 쪽 밑에 붙입니다(같으면 합친 쪽 랭크 +1).
4단계. 같은 그룹 질문: find(a) == find(b)이면 같은 집합입니다.
알고노트 시각화는 find가 루트를 찾는 경로와 경로 압축으로 트리가 납작해지는 모습을 단계별로 보여줍니다.
시간복잡도와 공간복잡도
| 연산 | 복잡도 |
|---|---|
| find / union | O(α(n)) ≈ O(1) |
| 공간 | O(n) |
α(n)은 역 아커만 함수로, 현실적인 입력에서 4 이하의 상수처럼 동작합니다.
예시로 따라가기
원소 {0, 1, 2, 3}이 각각 따로 있다고 합시다.
- •union(0, 1) → 0과 1이 한 그룹
- •union(2, 3) → 2와 3이 한 그룹
- •union(1, 2) → 두 그룹이 합쳐져
{0,1,2,3}하나 - •find(0) == find(3)? → 예 (모두 같은 대표)
자주 하는 실수
- •최적화 누락: 경로 압축과 랭크 합치기 중 하나라도 빠지면 트리가 선형으로 길어질 수 있습니다.
- •대표 비교 누락:
parent[a] == parent[b]로 비교하면 안 됩니다 — 반드시find로 루트를 구해 비교하세요. - •초기화:
parent[i] = i로 시작하지 않으면 루트 판정이 깨집니다.
알고노트에서 직접 확인하세요
원소들이 어떻게 그룹으로 합쳐지고, find가 루트를 찾으며 경로 압축으로 트리가 납작해지는지 알고노트에서 단계별로 확인할 수 있습니다.