유니온 파인드는 코딩 테스트용 자료 구조에 그치지 않습니다. 그래프 라이브러리, 이미지 처리, 컴파일러, 데이터 정제 파이프라인 곳곳에 들어 있습니다. 이 장에서는 실제 라이브러리에서 쓰는 방법과 자주 하는 실수, 더 읽을 자료를 정리합니다.
라이브러리에 들어 있는 유니온 파인드
직접 구현하기 전에 이미 쓰고 있는 라이브러리에 있는지 확인하세요.
- SciPy:
scipy.cluster.hierarchy.DisjointSet(SciPy 1.6부터)은 정수뿐 아니라 해시 가능한 어떤 객체도 원소로 받습니다. - NetworkX:
networkx.utils.UnionFind를 내부의 크루스칼 최소 신장 트리 구현 등에 사용합니다. - Boost: C++의 Boost Graph Library는
boost::disjoint_sets를 제공하며, 연결 요소 증분 계산에 씁니다. - 이미지 처리: scikit-image의
label이나 OpenCV의 connectedComponents 같은 연결 영역 라벨링은 두 번 훑는(two-pass) 방식에서 임시 라벨을 합칠 때 유니온 파인드와 같은 원리를 씁니다.
from scipy.cluster.hierarchy import DisjointSet
ds = DisjointSet(["a", "b", "c", "d"])
ds.merge("a", "b")
ds.merge("c", "d")
print(ds.connected("a", "c")) # False
ds.add("e")
ds.merge("b", "e")
print(sorted(map(sorted, ds.subsets()))) # [['a', 'b', 'e'], ['c', 'd']]
실제 시스템에서의 쓰임
- 네트워크와 인프라: 링크가 추가될 때 어떤 장비들이 서로 통신할 수 있는지 추적합니다.
- 데이터 정제와 엔티티 해석: 전화번호, 이메일, 기기 ID를 공유하는 레코드를 같은 고객으로 묶습니다.
- 컴파일러와 타입 검사: 타입 추론의 단일화(unification)와 Steensgaard 방식의 포인터 분석은 "같다"고 밝혀진 대상을 유니온 파인드로 합칩니다.
- 물리 시뮬레이션: 격자의 칸을 무작위로 열면서 위와 아래가 이어졌는지 확인하는 퍼컬레이션(percolation) 실험에 씁니다.
- 클러스터링: 거리가 기준보다 가까운 점끼리 합치면 단일 연결(single-linkage) 군집과 같은 결과가 나옵니다.
문자열 키 다루기
실무 데이터의 키는 대개 정수가 아닙니다. 딕셔너리로 처음 보는 키에 번호를 붙이면 배열 기반 DSU를 그대로 쓸 수 있습니다.
class KeyedDSU:
def __init__(self):
self.index, self.parent, self.size = {}, [], []
def _id(self, key):
if key not in self.index:
self.index[key] = len(self.parent)
self.parent.append(len(self.parent))
self.size.append(1)
return self.index[key]
def find(self, key):
x = self._id(key)
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.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
d = KeyedDSU()
d.union("phone:010-1234", "mail:kim@x.io")
d.union("mail:kim@x.io", "device:A7")
print(d.find("phone:010-1234") == d.find("device:A7")) # True
자주 하는 실수
- 루트가 아닌 원소끼리 연결:
parent[a] = b처럼 쓰면 집합이 깨집니다. 반드시 find로 찾은 루트끼리 연결합니다. - 부모 비교로 같은 집합 판정:
parent[a] == parent[b]는 경로 압축 전에는 틀릴 수 있습니다. 항상 find(a) == find(b)를 씁니다. - 1부터 시작하는 번호: 문제의 정점 번호가 1부터라면 배열을 n+1 크기로 만들거나 1을 빼서 씁니다.
- 깊은 재귀: Python에서 재귀 find는 큰 입력에서 RecursionError가 납니다. 반복문으로 씁니다.
- 삭제와 되돌리기: 기본 구조는 집합을 쪼갤 수 없습니다. 되돌리기가 필요하면 경로 압축을 빼고 변경 기록을 스택에 쌓는 롤백 DSU를 씁니다.
class RollbackDSU:
def __init__(self, n):
self.parent, self.size, self.history = list(range(n)), [1] * n, []
def find(self, x): # 경로 압축 없음: 되돌릴 수 있게 유지
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.history.append((rb, ra) if ra != rb else None)
if ra != rb:
self.parent[rb] = ra
self.size[ra] += self.size[rb]
def rollback(self):
last = self.history.pop()
if last:
rb, ra = last
self.parent[rb] = rb
self.size[ra] -= self.size[rb]
정리
유니온 파인드는 SciPy, NetworkX, Boost 같은 라이브러리와 이미지 라벨링, 타입 추론, 데이터 정제에 이미 쓰이고 있습니다. 루트끼리 연결하고 find로 비교하며 반복문으로 구현한다는 세 가지만 지켜도 대부분의 실수를 피할 수 있습니다. 되돌리기가 필요하면 롤백 DSU를 떠올리세요.
더 읽을거리
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.