Ch.7 그래프
Union-Find — 같은 편인지 묻는 자료구조
"너 우리 편이야?" 이 질문에 O(1)로 답하기
학교에서 조를 짭니다. 1번과 2번이 같은 조, 2번과 3번이 같은 조면 — 1번과 3번도 같은 조입니다. 이런 그룹 판별을 빠르게 하는 것이 Union-Find입니다.
그룹이 계속 합쳐지는데, 매번 모든 멤버를 확인해야 하나?
트리 구조로 각 그룹을 표현하면, find 연산으로 거의 O(1)에 같은 그룹인지 판별합니다.
핵심 개념
Union-Find(Disjoint Set)
서로소 집합 — 그룹 합치기/찾기 자료구조
find(x)
x가 속한 그룹의 대표(root)를 반환
union(x, y)
x와 y의 그룹을 하나로 합침
핵심 내용
그룹을 합치고 판별하는 Union-Find를 배웁니다
처음에는 모든 노드가 자기 자신이 대표입니다. union하면 한쪽 대표가 다른 쪽 아래로 들어갑니다
같은 그룹 판별: `find(x) == find(y)` — 루트가 같으면 같은 그룹!
Union-Find의 기본 구현을 단계별로 작성합니다
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두 가지 최적화 1. 경로 압축(Path Compression) — find 시 루트에 직접 연결 `self.parent[x] = self.find(self.parent[x])` 2. 랭크 합치기(Union by Rank) — 낮은 트리를 높은 트리에 붙임 트리가 한쪽으로 치우치는 것을 방지
두 최적화를 모두 적용하면 find/union 모두 거의 O(1) (정확히는 O(α(n)) ≈ O(1))
5개 노드로 Union-Find의 동작을 추적합니다
union(1,3) 시 1의 루트(0)와 3의 루트(2)를 합칩니다. 결국 {0,1,2,3}이 한 그룹, {4}가 독립 그룹
Union-Find로도 연결 요소 개수를 구할 수 있습니다
def count_components(n, edges):
uf = UnionFind(n)
for u, v in edges:
uf.union(u, v)
# 루트가 자기 자신인 노드 수 = 연결 요소 수
roots = set(uf.find(i) for i in range(n))
return len(roots)
print(count_components(5, [(0,1),(1,2),(3,4)])) # 2DFS vs Union-Find — 연결 요소 구하기 DFS: 인접 리스트 구축 → 방문 안 한 노드마다 DFS Union-Find: 엣지마다 union → 루트 개수 세기 두 방법 모두 O(V+E). 엣지가 동적으로 추가될 때는 Union-Find가 유리!
"두 원소가 같은 그룹인가?" + "그룹을 합쳐라" → Union-Find를 떠올리세요!
Union-Find에서 경로 압축의 역할은?
경로 압축과 랭크 합치기를 모두 적용한 Union-Find의 find 시간 복잡도는 O(log n)이다
Union-Find 정복!
핵심 용어
parent 배열
각 노드의 부모를 저장 — 초기값은 자기 자신
find(x)
x의 루트(대표)를 찾아 반환
union(x, y)
x, y의 루트를 연결하여 그룹 합치기
정리 노트
Union-Find (Disjoint Set)
핵심 연산
- find(x)
- x의 루트를 찾음 — 경로 압축 적용
- union(x, y)
- 두 그룹 합침 — 랭크 합치기 적용
- 시간 복잡도
- 거의 O(1) — O(α(n))
활용
- 연결 요소
- union 후 루트 개수 = 연결 요소 수
- 사이클 감지
- union 전 이미 같은 루트 → 사이클!
"같은 그룹인가?" + "그룹 합치기" = Union-Find! 클래스 템플릿을 통째로 외우세요.
시각 자료
핵심 정리
- 1Union-Find = 그룹 합치기(union) + 그룹 판별(find)
- 2경로 압축 + 랭크 합치기로 거의 O(1)
- 3연결 요소, 사이클 감지에 활용
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작