동작 원리: find와 union 따라가기

이 장에서는 원소 8개(0~7)로 작은 예제를 직접 따라가며 parent 배열이 어떻게 바뀌는지 봅니다. 먼저 최적화가 없을 때 트리가 어떻게 나빠지는지 확인하고, 크기 기준 합치기와 경로 압축이 그 문제를 어떻게 해결하는지 살펴봅니다.

시작 상태

처음에는 모든 원소가 혼자 있는 집합이므로 자기 자신이 부모입니다. 크기 배열은 모두 1입니다.

최적화 없이 합칠 때의 문제

항상 "두 번째 루트를 첫 번째 루트 밑에" 붙인다고 해 봅시다. union(1, 0), union(2, 1), union(3, 2) 순서로 호출하면 0이 1 밑에, 1이 2 밑에, 2가 3 밑에 붙어 0 → 1 → 2 → 3 같은 한 줄짜리 트리가 생깁니다. 이제 find(0)은 루트 3까지 세 번을 올라가야 합니다. 원소가 n개면 최악의 경우 find 한 번이 O(n)이 됩니다.

parent = list(range(8))

def find(x):
    steps = 0
    while parent[x] != x:
        x = parent[x]
        steps += 1
    return x, steps

def naive_union(a, b):
    ra, _ = find(a)
    rb, _ = find(b)
    if ra != rb:
        parent[rb] = ra

for i in range(1, 4):
    naive_union(i, i - 1)   # 0 → 1 → 2 → 3
print(find(0))  # (3, 3): 루트 3까지 3단계

크기 기준 합치기(union by size)

해결책은 작은 트리를 큰 트리 밑에 붙이는 것입니다. 그러면 어떤 원소의 깊이가 1 늘어날 때마다 그 원소가 속한 집합의 크기는 적어도 두 배가 됩니다. 집합 크기는 n을 넘을 수 없으므로 깊이는 최대 log2 n입니다. 랭크(높이의 상한)를 기준으로 삼는 union by rank도 같은 보장을 줍니다.

같은 8개 원소로 다음 순서를 크기 기준으로 실행해 봅시다. union은 먼저 두 인자에 find를 호출해 루트를 구합니다.

6단계가 끝나면 집합은 {0, 1, 2, 3, 7}과 {4, 5, 6} 두 개입니다. 원소 3의 경로는 3 → 2 → 0으로 길이 2이고, 8개 원소에서 가능한 최대 깊이 3을 넘지 않습니다.

경로 압축(path compression)

find(3)을 호출하면 3 → 2 → 0을 지나 루트 0을 찾습니다. 경로 압축은 이때 지나간 노드들의 부모를 곧바로 루트로 바꿔 둡니다. 다음에 find(3)을 부르면 한 번만 올라가면 됩니다.

def find(x):
    root = x
    while parent[root] != root:      # 1차: 루트 찾기
        root = parent[root]
    while parent[x] != root:         # 2차: 지나온 노드를 루트에 직접 연결
        parent[x], x = root, parent[x]
    return root

경로 압축은 find 안에서 자동으로 일어나므로 호출하는 쪽에서는 따로 신경 쓸 필요가 없습니다. 같은 원소를 여러 번 조회할수록 경로가 짧아져 이득이 커집니다.

반복문 두 번 대신 한 번에 처리하는 경로 반감(path halving)도 많이 씁니다. 지나가면서 각 노드를 할아버지 노드에 붙이는 방식으로, 코드가 짧고 성능 보장은 같습니다.

def find_halving(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]  # 할아버지로 건너뛰기
        x = parent[x]
    return x

압축 전후 비교

parent[3]이 2에서 0으로 바뀌었습니다. 압축은 트리 모양만 납작하게 만들 뿐 어느 원소가 어느 집합에 속하는지는 바꾸지 않습니다. 크기 배열도 루트의 값만 의미가 있으므로 압축 중에 고칠 필요가 없습니다.

정리

최적화 없는 유니온 파인드는 트리가 한 줄로 길어져 느려질 수 있습니다. 작은 트리를 큰 트리 밑에 붙이는 크기·랭크 기준 합치기가 트리 높이를 log n으로 묶고, 경로 압축이나 경로 반감이 find 때마다 트리를 납작하게 만듭니다. 두 기법은 서로 독립적이며 함께 쓸 때 가장 빠릅니다.