유니온-파인드(Union-Find, Disjoint Set Union)는 원소들을 서로소 집합으로 관리하는 자료구조다. Union(합치기)과 Find(찾기) 연산을 거의 O(1)에 처리하며, 최소 신장 트리(크루스칼), 네트워크 연결 확인 등에 활용된다.
구현
python
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 경로 압축
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False # 이미 같은 집합
# 랭크 기반 합치기
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
uf = UnionFind(6)
uf.union(0, 1)
uf.union(2, 3)
uf.union(1, 3)
print(uf.find(0) == uf.find(3)) # True (같은 집합)
print(uf.find(0) == uf.find(4)) # False (다른 집합)
시간 복잡도
경로 압축 + 랭크 최적화 적용 시:
- •Find: O(α(n)) ≈ O(1) (역 아커만 함수)
- •Union: O(α(n)) ≈ O(1)
활용 사례
- •크루스칼 알고리즘 — 사이클 검사
- •네트워크 연결 여부 확인
- •픽셀 클러스터링 (그림판 색 채우기)
- •블록체인 포크 검사
관련 개념
- •그래프 — 유니온-파인드로 그래프 구성 요소 관리
- •크루스칼 — 유니온-파인드 핵심 활용
참고문헌
- •Cormen et al. Introduction to Algorithms — Chapter 21
