유니온 파인드(분리 집합)란? 동작 원리, 코드, 시간 복잡도

유니온 파인드가 해결하는 문제

케이블을 한 번에 하나씩 추가하는 컴퓨터 네트워크를 상상해 보세요. 케이블을 추가할 때마다 "컴퓨터 A와 컴퓨터 B가 연결되어 있나?"에 답해야 합니다. 질문마다 그래프 탐색을 하면 매번 O(n + m)이 듭니다. 유니온 파인드는 케이블이 추가될 때마다 연결된 그룹을 유지하므로 각 질문에 거의 O(1)로 답합니다.

같은 필요가 크루스칼 최소 신장 트리 알고리즘(두 끝점이 이미 같은 트리에 속하는가?), 무방향 그래프의 사이클 탐지, 같은 이메일을 쓰는 계정 묶기, 침투(percolation) 시뮬레이션, 이미지 처리에서 연결된 영역에 레이블 붙이기에서도 나타납니다.

쉬운 말로 설명하는 원리

모든 요소는 부모를 가리킵니다. 자기 자신을 가리키는 요소가 루트이며, 루트가 그룹 전체의 대표입니다. x의 그룹을 찾으려면 루트에 도달할 때까지 부모 포인터를 따라갑니다. 두 그룹을 합치려면 두 루트를 찾아 한쪽 루트가 다른 쪽을 가리키게 합니다.

트리를 납작하게 유지하는 최적화가 두 가지 있습니다.

• 랭크(또는 크기) 기반 합치기: 더 낮은(또는 더 작은) 트리를 더 높은(또는 더 큰) 트리 아래에 붙이므로, 트리의 높이는 같은 크기의 두 트리를 합칠 때만 커집니다.
• 경로 압축: find를 하는 동안 경로상의 모든 노드가 루트를 직접 가리키게 하여 다음 조회는 한 단계로 끝나게 합니다.

예제: 요소 다섯 개

0부터 4까지의 요소가 각각 자기 그룹에 있는 상태에서 시작합니다. 부모 배열은 [0, 1, 2, 3, 4]입니다. 크기 기반 합치기를 쓰며, 크기가 같으면 두 번째 루트를 자식으로 만듭니다.

파이썬 구현

이 버전은 크기 기반 합치기와, 경로 압축을 적용한 반복식 find를 사용하므로 재귀 깊이 문제가 없습니다. union은 두 요소가 이미 같은 그룹이었다면 False를 반환하며, 사이클 탐지에 유용합니다.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.groups = n

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:       # path compression
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                    # already connected
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra                 # ra is the larger root
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.groups -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)

uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(1, 3)
print(uf.find(3), uf.parent)       # 0 [0, 0, 0, 0, 4]
print(uf.connected(1, 4), uf.groups)  # False 2

예제: 무방향 그래프의 사이클 탐지

간선을 하나씩 처리합니다. 간선의 두 끝점이 이미 같은 루트를 가지고 있다면 그 간선은 사이클을 닫습니다. 크루스칼 알고리즘은 간선을 가중치 순으로 정렬한 뒤 정확히 이 검사를 사용합니다.

def has_cycle(n, edges):
    uf = UnionFind(n)
    for a, b in edges:
        if not uf.union(a, b):
            return True
    return False

print(has_cycle(4, [(0, 1), (1, 2), (2, 3)]))  # False
print(has_cycle(4, [(0, 1), (1, 2), (2, 0)]))  # True

시간 복잡도와 공간 복잡도

α(n)은 역아커만 함수로, 실제 컴퓨터에 담길 수 있는 어떤 n에 대해서도 4 이하일 만큼 아주 느리게 증가합니다. 실질적으로는 연산당 상수 시간이라는 뜻입니다. 이 한계는 1975년 로버트 타잔(Robert Tarjan)이 증명했습니다. 공간은 부모 배열과 크기 배열에 대해 O(n)입니다.

변형과 흔한 실수

• 루트가 아니라 요소끼리 비교하는 실수: union은 a와 b 자체가 아니라 find(a)와 find(b)를 연결해야 합니다.
• parent[x]가 대표라고 가정하는 실수. 합치기를 한 뒤에는 find(x)만 올바르므로, 부모로 그룹을 묶기 전에 모든 요소에 find를 호출하세요.
• 랭크 기반 합치기 없이 큰 입력에 재귀 find를 쓰면 파이썬의 재귀 한도에 걸릴 수 있습니다. 위의 반복식 버전은 이를 피합니다.
• 요소가 0부터 n-1까지의 정수가 아닌 경우: 먼저 dict로 인덱스에 매핑하거나, 부모를 dict에 저장하고 요소를 필요할 때 추가하세요.
• 유니온 파인드는 그룹을 분리할 수 없습니다. 간선이 삭제된다면 다른 자료구조나, 삭제를 거꾸로 처리하는 오프라인 방식이 필요합니다.
• 가중치 유니온 파인드는 각 노드에 부모까지의 오프셋을 저장하여 "a가 b보다 얼마나 더 무거운가?" 같은 질문에 답합니다.

언제 쓰는가와 대표 문제

그룹이 합쳐지기만 하고, 두 요소가 같은 그룹인지 또는 그룹이 몇 개인지를 물을 때 유니온 파인드를 사용하세요. 변하지 않는 그래프에서 연결성 질문이 한 번뿐이라면 단순한 BFS나 DFS가 더 간단합니다. 실제 경로가 필요하면 유니온 파인드는 소속만 알기 때문에 그래프 탐색을 쓰세요.

대표 문제: 연결 요소의 개수, 섬의 개수(격자 칸을 요소로 사용), 중복 연결(사이클을 만드는 간선), 계정 합치기, a == b, b != c 같은 등식 방정식의 만족 가능성, 크루스칼 최소 신장 트리.