유니온 파인드(Union-Find)는 원소들을 겹치지 않는 여러 묶음으로 나누어 관리하는 자료 구조입니다. 서로소 집합(disjoint set) 자료 구조, 줄여서 DSU(Disjoint Set Union)라고도 부릅니다. 이 장에서는 유니온 파인드가 다루는 문제, 핵심 연산 두 가지, 그리고 이 주제를 공부할 때 자주 나오는 용어를 정리합니다.
서로소 집합이란
두 집합에 공통 원소가 하나도 없으면 두 집합은 서로소(disjoint)입니다. 원소 전체를 서로소인 집합 여러 개로 빠짐없이 나눈 것을 분할(partition)이라고 합니다. 예를 들어 원소 0부터 5까지를 {0, 1, 2}, {3, 4}, {5}로 나누면 모든 원소가 정확히 한 집합에만 들어 있습니다.
유니온 파인드는 이런 분할을 저장해 두고, 다음 두 질문에 빠르게 답하도록 설계되었습니다.
- find(x): 원소 x가 속한 집합은 무엇인가? 정확히는 그 집합의 대표 원소(representative)를 돌려줍니다.
- union(a, b): a가 속한 집합과 b가 속한 집합을 하나로 합칩니다.
두 원소가 같은 집합인지 알고 싶다면 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
숲(forest)으로 표현하기
유니온 파인드는 각 집합을 하나의 트리로, 전체를 여러 트리의 모임인 숲으로 표현합니다. 원소마다 부모 하나만 기억하고, 자기 자신이 부모인 원소가 트리의 루트, 즉 그 집합의 대표입니다. 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)라는 두 가지 최적화를 함께 씁니다. 두 기법은 다음 장에서 자세히 다룹니다.
언제 쓰는가
- 간선이 하나씩 추가되는 그래프에서 연결 요소(connected component)를 추적할 때
- 크루스칼(Kruskal) 알고리즘으로 최소 신장 트리를 만들 때
- 무방향 그래프에 사이클이 생기는지 확인할 때
- 같은 이메일을 쓰는 계정처럼 "같다"는 관계로 항목을 묶을 때
유니온 파인드는 두 원소가 연결되어 있는지만 알려 줄 뿐, 어떤 경로로 이어져 있는지는 알려 주지 않습니다. 실제 경로나 최단 거리가 필요하면 BFS나 DFS 같은 그래프 탐색을 써야 합니다. 또 질문이 모두 끝난 뒤 한 번만 답하면 되는 정적인 그래프라면 DFS 한 번으로 연결 요소를 구하는 편이 더 간단할 수 있습니다.
반대로 집합을 다시 쪼개거나 원소를 삭제해야 한다면 기본 유니온 파인드로는 부족합니다. 합치기만 가능하다는 제약을 기억해 두세요.
용어 정리
# 같은 집합인지 묻는 함수는 find 두 번이면 충분하다
def connected(a, b):
return find(a) == find(b)
print(connected(0, 2), connected(2, 3)) # True False
정리
유니온 파인드는 서로소 집합의 분할을 parent 배열 하나로 저장하고, find로 대표 원소를 찾고 union으로 두 집합을 합칩니다. 관계가 전이적이고 연결이 늘어나기만 하는 문제에서 특히 강력하며, 최적화 두 가지를 더하면 거의 상수 시간에 동작합니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.