출시·고도화 중
유니온 파인드 안내서 · 1/6
유니온 파인드(Union-Find)는 원소들을 겹치지 않는 여러 묶음으로 나누어 관리하는 자료 구조입니다. 서로소 집합(disjoint set) 자료 구조, 줄여서 DSU(Disjoint Set Union)라고도 부릅니다. 이 장에서는 유니온 파인드가 다루는 문제, 핵심 연산 두 가지, 그리고 이 주제를 공부할 때 자주 나오는 용어를 정리합니다.
두 집합에 공통 원소가 하나도 없으면 두 집합은 서로소(disjoint)입니다. 원소 전체를 서로소인 집합 여러 개로 빠짐없이 나눈 것을 분할(partition)이라고 합니다. 예를 들어 원소 0부터 5까지를 {0, 1, 2}, {3, 4}, {5}로 나누면 모든 원소가 정확히 한 집합에만 들어 있습니다.
유니온 파인드는 이런 분할을 저장해 두고, 다음 두 질문에 빠르게 답하도록 설계되었습니다.
두 원소가 같은 집합인지 알고 싶다면 find(a) == find(b)를 비교하면 됩니다. 집합 이름을 따로 붙이지 않고 집합 안의 원소 하나를 대표로 삼는 것이 핵심입니다.
학교에서 처음에는 모두가 혼자라고 생각해 봅시다. "철수와 영희가 친구가 됐다", "영희와 민수가 친구가 됐다" 같은 소식이 하나씩 들어올 때마다 두 사람이 속한 모임을 합칩니다. 그러면 철수와 민수는 직접 아는 사이가 아니어도 같은 모임에 속합니다. 이처럼 관계가 전이적으로 이어지고, 연결은 늘어나기만 하며, 질문은 "같은 모임인가?"뿐인 상황이 유니온 파인드가 가장 잘 맞는 문제입니다.
가장 단순한 구현은 원소마다 모임 번호를 적어 두는 것입니다. find는 바로 답할 수 있지만 union을 할 때마다 배열 전체를 훑어야 합니다.
# 단순한 방식(quick-find): union 한 번에 O(n)
label = list(range(6))
def find(x):
return label[x]
def union(a, b):
la, lb = label[a], label[b]
for i in range(len(label)):
if label[i] == lb:
label[i] = la
union(0, 1)
union(1, 2)
print(find(2) == find(0)) # True유니온 파인드는 각 집합을 하나의 트리로, 전체를 여러 트리의 모임인 숲으로 표현합니다. 원소마다 부모 하나만 기억하고, 자기 자신이 부모인 원소가 트리의 루트, 즉 그 집합의 대표입니다. find는 부모를 따라 루트까지 올라가고, union은 한 루트를 다른 루트 밑에 붙이기만 하면 됩니다.
parent = list(range(6)) # 처음에는 모두 자기 자신이 루트
def find(x):
while parent[x] != x:
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra != rb:
parent[rb] = ra # 루트끼리만 연결한다
union(0, 1); union(1, 2); union(3, 4)
print([find(x) for x in range(6)]) # [0, 0, 0, 3, 3, 5]위 코드를 실행한 뒤 parent 배열은 [0, 0, 0, 3, 3, 5]입니다. 자기 자신을 가리키는 칸이 0, 3, 5 세 개이므로 집합도 세 개입니다. 이처럼 루트의 개수가 곧 집합의 개수이며, 집합을 합칠 때마다 루트가 하나씩 줄어듭니다.
이 기본형은 트리가 한 줄로 길어지면 find가 느려집니다. 그래서 실제로는 경로 압축(path compression)과 랭크·크기 기준 합치기(union by rank/size)라는 두 가지 최적화를 함께 씁니다. 두 기법은 다음 장에서 자세히 다룹니다.
유니온 파인드는 두 원소가 연결되어 있는지만 알려 줄 뿐, 어떤 경로로 이어져 있는지는 알려 주지 않습니다. 실제 경로나 최단 거리가 필요하면 BFS나 DFS 같은 그래프 탐색을 써야 합니다. 또 질문이 모두 끝난 뒤 한 번만 답하면 되는 정적인 그래프라면 DFS 한 번으로 연결 요소를 구하는 편이 더 간단할 수 있습니다.
반대로 집합을 다시 쪼개거나 원소를 삭제해야 한다면 기본 유니온 파인드로는 부족합니다. 합치기만 가능하다는 제약을 기억해 두세요.
| 용어 | 뜻 |
|---|---|
| 대표 원소 | 집합을 가리키는 원소, 트리의 루트 |
| parent 배열 | 원소마다 부모를 적어 둔 배열 |
| 랭크(rank) | 트리 높이의 상한으로 쓰는 값 |
| 크기(size) | 집합에 들어 있는 원소 수 |
| 경로 압축 | find 중에 지나간 노드를 루트 가까이 붙이는 기법 |
| 분할 상환 | 연산 여러 번의 평균 비용으로 성능을 따지는 방식 |
# 같은 집합인지 묻는 함수는 find 두 번이면 충분하다
def connected(a, b):
return find(a) == find(b)
print(connected(0, 2), connected(2, 3)) # True False유니온 파인드는 서로소 집합의 분할을 parent 배열 하나로 저장하고, find로 대표 원소를 찾고 union으로 두 집합을 합칩니다. 관계가 전이적이고 연결이 늘어나기만 하는 문제에서 특히 강력하며, 최적화 두 가지를 더하면 거의 상수 시간에 동작합니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.
첫 댓글을 남겨 보세요.