union-find란 무엇이며 어디에 사용되나요?

Question

Accepted Answer

**Union-Find**(Disjoint Set Union, 서로소 집합)는 원소들을 **서로소 집합**으로 분할하여 추적하며 거의 O(1)인 두 연산을 지원합니다. **find**(x는 어느 집합에 있는가?)와 **union**(두 집합을 병합)입니다. **연결성** 질의에 탁월합니다.

## 개념

각 집합은 대표 루트를 가진 트리입니다. **path compression(경로 압축)**과 **union by rank/size(랭크/크기 기준 합치기)**를 사용하면 연산이 거의 상수의 **분할 상환** 시간(역 Ackermann, α(n))에 실행됩니다.

## 예시

```python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # 압축
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # 이미 연결됨
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra           # 작은 것을 큰 것 아래에 붙임
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True
```

## 복잡도

- **find / union:** O(α(n)) ≈ 분할 상환 O(1). **공간:** O(n).

## 응용

- **Kruskal의 MST** — 간선 추가 시 사이클 탐지.
- **연결 요소** / 동적 연결성.
- 무방향 그래프의 **사이클 탐지**.
- **퍼콜레이션**, 이미지 분할, 계정/네트워크 병합.

## 함정

path compression과 union by rank가 없으면 트리가 O(n) 사슬로 퇴화합니다. 집합의 효율적인 *분할*은 지원하지 않습니다.

## 왜 중요한가

Union-find는 "이 두 가지가 연결되어 있는가?"를 대규모로 거의 비용 없이 답합니다.

Kruskal의 MST와 많은 그래프 및 클러스터링 알고리즘 내부의 엔진입니다.

그 두 가지 최적화는 작은 구조적 기법이 어떻게 거의 상수 시간 성능을 내는지에 대한 기억에 남는 교훈입니다.