[알고리즘] Union-Find

정의

• 대표적 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가진다
• 서로소 집합(Disjoint-Set) 알고리즘이라고도 부른다
• 여러 노드가 존재할 때, 두 개의 노드를 선택해서 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

동작

Union-Find 알고리즘은 Find와 Union 총 두 개의 동작으로 이루어진다.

1. Find

해당 노드의 부모 노드를 찾는 동작이다. 부모 노드로 자기 자신을 가리킬 때까지(= 부모 노드가 없을 때까지) 순회하며 찾는다

def find(i):
	# 자기 자신을 가리킨다면 자기 자신이 부모 노드이다
	if parent[i] == i:
    	return i
    return find(parent[i])

시간 복잡도

최악의 경우 O(n) 의 복잡도를 갖는다

2. Union

두 노드를 인자로 받아 합치는 동작이다. 즉, 같은 부모 노드를 가리키도록 한다

def union(parent, i, j):
	# 각 노드의 부모 노드를 찾는다
	parent_i = find(parent, i)
    parent_j = find(parent, j)
    
    # 통상적으로 작은 값으로 합친다
    if (parent_i < parent_j) parent[parent_j] = parent_a
    else parent[parent_i] = parent_j

시간 복잡도

최악의 경우 O(n) 의 복잡도를 갖는다

이렇게 완성된 parent 배열에 대해 두 노드가 같은 부모를 가리키는지 찾기 위한 알고리즘이다.

참고 링크

Union-Find (합집합 찾기)
Introduction to Disjoint Set (Union-Find Algorithm)