경로 압축과 랭크 기반 합집합을 사용하는 disjoint-set(union-find) 구조란 무엇인가요?

Question

Accepted Answer

**disjoint-set(서로소 집합, union-find)**은 겹치지 않는 그룹으로 분할된 원소들을 추적하며, "**이 둘이 같은 그룹에 있는가?**"와 "**두 그룹을 병합하라**"를 **거의 상수 시간**에 답합니다. **경로 압축(path compression)**과 **랭크 기반 합집합(union by rank)**을 사용하면 두 연산 모두 **O(α(n))**으로 동작합니다. 사실상 O(1)입니다(α는 역 아커만 함수).

## 동작 방식

각 집합은 트리이고, **루트**가 집합의 대표입니다. `find`는 루트까지 걸어가고, `union`은 한 루트를 다른 루트 아래에 연결합니다.

```text
find(x): 부모를 따라 루트까지 감
union(a,b): 더 짧은 트리를 더 큰 트리 아래에 붙임(랭크 기준)
경로 압축: find 후, 노드들이 루트를 직접 가리키게 함
   이전:  a->b->c->root      이후:  a->root, b->root, c->root
```

## 코드

```python
class DSU:
    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 | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## 일반적인 용도

- **Kruskal의 MST** — 사이클을 만들지 않고 컴포넌트를 병합함.
- 그래프나 격자에서의 **연결 컴포넌트**.
- **동적 연결성(dynamic connectivity)**과 네트워크/침투 문제.

## 왜 중요한가

union-find는 그렇지 않으면 반복적인 O(n) 그래프 순회가 필요할 그룹핑과 연결성 문제를, 질의당 거의 O(1)로 축소하여 해결합니다.

점진적으로 집합을 병합하고 연결성을 테스트해야 할 때마다 쓰이는 필수 도구이며, 시니어 레벨 면접에서 자주 등장하는 주제입니다.