[알고리즘] 유니온 파인드

Union-Find (합집합 찾기 알고리즘) = Union 연산 + 루트를 찾는 Find 연산

• 두 노드가 같은 집합에 속하는지 판별하는 그래프 알고리즘
• Disjoin Set: 서로소 집합(상호 배타적 집합)

 

★ Find(x)

1. 원소 x가 속한 집합의 대표(루트)를 찾는 함수.
2. 경로 압축(Path Compression) 기법을 써서 효율성을 높을 수 있음.

※ 자신의 부모 노드만 저장하게 되면 재귀 호출을 통한 탐색에 시간이 많이 들기 때문에,

인접한 부모 노드가 아니라 루트 노드의 번호를 저장해야함!

 

★ Union(x, y)

1. 원소 x와 y가 속한 두 집합을 하나로 합치는 함수.
2. 대표 노드를 기준으로 한 집합으로 병합.

# 초기
1   2   3   4   5
↑   ↑   ↑   ↑   ↑
자기 자신이 루트

# union(1, 2)
1 - 2   3   4   5
↑   ↑
root = 1

# union(3, 4)
1 - 2   3 - 4   5
          ↑ 
       root = 3

# union(2, 3)
1 - 2 - 3 - 4   5
↑
root = 1

 

 

# 초기화 1~n
parent = [i for i in range(n+1)]

# Find (with path compression)
def find(x):
    if paraent[x] != x:
    	parent[x] = find(parent[x])
    return parent[x]
    
# Union
def union(a, b):
    root_a = find(a)
    root_b = find(b)
    if root_a != root_b:
    	parent[root_b] = root_a