metanoia95의 기술 블로그

Union-Find(유니온-파인드)는 여러 원소를 집합(Set)으로 관리하면서, 두 원소가 같은 집합에 속하는지 빠르게 확인하고 집합을 합치는 자료구조입니다.

최소 신장 트리의 크루스칼(Kruskal) 알고리즘에서 사이클이 생기는지 확인하기 위해 가장 많이 사용됩니다.

핵심 연산

원소 x가 속한 집합의 대표(루트)를 찾습니다.

예를 들어,

1
├── 2
└── 3

이라면

Find(1) = 1
Find(2) = 1
Find(3) = 1

즉, 모두 같은 집합입니다.

a와 b가 속한 두 집합을 하나로 합칩니다.

예를 들어 처음에는

1   2   3   4

모두 독립적인 집합입니다.

Union(1,2)를 하면

1
└──2

3

4

Union(3,4)를 하면

1
└──2

3
└──4

Union(2,3)를 하면

1
├──2
└──3
    └──4

이제 1,2,3,4는 모두 같은 집합입니다.

간선을 하나씩 선택할 때

A ----- B
 \     /
  \   /
    C

이미

를 선택한 상태에서

A-C를 또 선택하면

A
|\
| \
|  \
B---C

사이클이 생깁니다.

이를 확인하려면

Find(A) == Find(C)

를 검사하면 됩니다.

보통 부모 배열 하나만 있으면 됩니다.

parent = [0, 1, 2, 3, 4]

초기에는 자기 자신이 부모입니다.

def find(x):
    if parent[x] == x:
        return x
    return find(parent[x])

def union(a, b):
    ra = find(a)
    rb = find(b)

    if ra != rb:
        parent[rb] = ra

실제로는 두 가지 최적화를 함께 사용합니다.

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

한 번 find()를 수행하면 중간 노드들이 모두 루트를 직접 가리키게 되어 이후 탐색이 매우 빨라집니다.

예를 들어,

1
└──2
    └──3
        └──4

에서 find(4)를 한 번 수행하면

1
├──2
├──3
└──4

처럼 모두 루트를 바로 가리키게 됩니다.

항상 더 작은 트리를 큰 트리 밑으로 붙여 트리의 높이가 커지는 것을 방지합니다.

최적화(Path Compression + Union by Rank)를 함께 사용하면

정확히는 O(α(N))이며, 여기서 α(N)은 역 아커만 함수(Inverse Ackermann Function)입니다. 이 함수는 현실적인 입력 크기에서는 5를 넘지 않을 정도로 매우 천천히 증가하므로, 사실상 상수 시간으로 취급합니다.