유니온 파인드 안내서 · 6/6

실무 활용과 주의할 점

유니온 파인드는 코딩 테스트용 자료 구조에 그치지 않습니다. 그래프 라이브러리, 이미지 처리, 컴파일러, 데이터 정제 파이프라인 곳곳에 들어 있습니다. 이 장에서는 실제 라이브러리에서 쓰는 방법과 자주 하는 실수, 더 읽을 자료를 정리합니다.

라이브러리에 들어 있는 유니온 파인드

직접 구현하기 전에 이미 쓰고 있는 라이브러리에 있는지 확인하세요.

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를 떠올리세요.

더 읽을거리

이 장에 대해 질문이 있나요?