Union-Find 알고리즘의 최적화 기법

박세환·2025년 4월 23일

단순한 Union-Find 알고리즘

def find_parent(a):
    if a == parent[a]:
        return a
    return find_parent(parent[a])

def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())
parent = list(range(v+1))

for _ in range(e):
    a, b = map(int, input().split())
    union_parent(a, b)

경로 압축

문제

현재 노드의 루트 노드를 find할 때마다 모든 직계 조상 노드를 탐색해야 한다.
(a,b)가 노드 a와 b 사이에 간선이 있음을 의미할 때, (3,4), (2,3), (1,2)가 주어지면 트리가 다음과 같이 구성된다.

다음으로 (4,5)가 주어지면, 4번 노드는 루트 노드를 찾기 위해 3 -> 2 -> 1을 거쳐 탐색해야 1번 노드를 찾을 수 있다.

경로 압축 기법을 추가하면 이러한 비효율을 줄일 수 있다.

find 재귀 호출하면서 부모 테이블 갱신하기

find 함수를 다음과 같이 수정하면 된다.

def find_parent(a):
    if a != parent[a]:
        parent[a] = find_parent(parent[a])
    return parent[a]

find 도중에 거쳐가는 non-root internal 노드의 부모도 루트 노드가 되도록 트리가 재구성되는 효과가 있다. 마지막으로, 모든 노드에 대해 find를 해 주면 트리의 깊이가 1이 되도록 완전히 재구성된다.

Rank

문제

경로 압축을 적용해도, (3,4), (2,3), (1,2)를 순서대로 입력했을 때 트리가 일직선으로, 비효율적으로 구성되는 문제는 피할 수 없다. (트리 구성 이후에 모든 노드에 대해 find 한 번씩 해 주면 트리가 평탄화되기는 한다.)

union으로 서로의 root를 연결하는 작업은 크게 보면 트리와 트리를 이어 붙이는 것이다. 트리의 깊이를 알고 있다면, 깊이가 작은 트리를 깊이가 큰 트리의 루트에 이어 붙여 깊이가 깊어지는 현상을 최소화할 수 있다.

Union 시 Rank로 부모 선택하기

union 함수를 다음과 같이 수정하면 된다.

def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if ranks[a] < ranks[b]:
        a, b = b, a
    elif ranks[a] == ranks[b]:
        ranks[a] += 1
    parents[b] = a

rank[i]는 i번째 노드를 루트 노드로 하는 트리의 깊이를 나타낸다.
기존 union 함수에서는 단순히 노드 번호가 작은 것이 부모 노드가 되게 했다면, 변경된 함수에서는 깊이가 작은 트리의 루트 노드가 깊이가 큰 트리의 루트 노드에 붙게 되어 전체 트리의 깊이가 최소한으로 늘어난다.