[Python] 유니온 파인드(Union-Find) 알고리즘

1️⃣ 기본 개념

서로소 집합(Disjoint Set) 자료구조를 관리하는 알고리즘이다.

 

두 가지 연산을 수행한다.

1. Find: 특정 원소가 속한 집합의 대표 원소를 찾는다.
2. Union: 두 원소가 속한 집합을 하나의 새로운 집합으로 통합한다.

집합을 트리 구조로 표현하며 트리의 루트 노드가 집합의 대표 원소가 된다.

 

2️⃣ 시간 복잡도

$ O(\alpha(N)) $ 로, N의 크기에 관계없이 매우 빠른 연산이 가능하다

$\alpha(N)$은 아커만 함수(Ackermann function)의 역함수이다.

 

3️⃣ 동작 과정

1. 초기화: 모든 원소에 대해 자기 자신을 부모로( $\text{parent}[i] = i$ ) 설정한 N개의 집합을 만든다
2. Find 동작: 원소의 루트를 찾기 위해 $\text{parent}[x]$를 따라 재귀적으로 올라간다. 루트에 도달하면 경로상의 노트가 루트를 가리키도록 부모를 갱신한다.
3. Union 동작: 합치려는 두 완소의 루트를 찾고 두 루트 중 하나를 다른 하나의 자식으로 연결하여 두 집합을 합친다.

 

4️⃣ 동작 예시

원소 (0, 1, 2, 3, 4)에 대해 $\text{Union}(1, 2)$, $\text{Union}(3, 4)$, $\text{Union}(1, 4)$를 수행하는 과정이다.

 

단계	연산	Find 결과 (rootA​,rootB​)	parent 배열
초기	-	-	[0, 1, 2, 3, 4]	5개 독립 집합
1	Union(1,2)	(1, 2)	[0, 1, 1, 3, 4]	1이 2의 부모가 됨
2	Union(3,4)	(3, 4)	[0, 1, 1, 3, 3]	3이 4의 부모가 됨
3	Union(1,4)	Find(1)→1 Find(4)→3	[0, 1, 1, 1, 3]	1이 3의 부모가 됨 (root1​=1,root4​=3)
4	Find(4)	-	[0, 1, 1, 1, 1]	경로 압축 발생: $\text{parent}[4]$가 3에서 1로 갱신됨

 

5️⃣ 예시 코드

# 부모 정보 저장 배열
parent = [i for i in range(n+1)]

# Find: 내 부모가 나 자신이 아니면, 부모를 계속 찾아 올라감 (경로 압축)
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

# Union: 두 집합의 대표를 찾아서 하나로 병합
def union(x, y):
    x = find(x)
    y = find(y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y

 

⚠️ 주의

• 파이썬의 경우, 기본 재귀 깊이가 제한되어 있어 한도를 늘려줘야 한다.
• 최적화 없이는 시간 초과가 발생할 수 있다.
• Union 연산은 항상 두 집합의 대표 노드를 연결한는 것!

 

💡 활용 사례

• 최소 신장 트리(MST)
• 그래프 연결 요소
• 네트워크 연결
• 게임 맵/퍼즐