[UnionFind] DisjointSet 찾기

참고 포스팅

https://ratsgo.github.io/data%20structure&algorithm/2017/11/12/disjointset/

 

서로소 집합(Disjoint Set)이란:

서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조.

 

다른 의미로는 그래프에서 Connected Components 들을 찾는 과정의 의미와 동치이다.

 

그렇다면 Connected components라는 것은 무엇일까?

다음 글을 참고해보자

 

In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths. 

 

즉, 2개의 vertex가 한번이라도 연결되어 있는 경로가 존재할 때 하나의 connected component를 구축하게 된다. 

 

위 그림에서는 총 3개의 connected component가 존재하게 된다. 그리고 이 녀석들은 서로가 서로소(Disjoint set)가 된다. 

 

그리고 이러한 disjoint set은 전체 집합이 있을 때, 구성 원소들이 겹치지 않도록 분할(partition)하는 데 자주 쓰인다.

 

임의의 set을 분할(partition)한다는 것은 각 부분 집합이 다음 2가지 속성을 만족하도록 set을 분할함을 의미한다.

• 각 부분 집합을 합치면 원래의 전체 집합이 된다
• partition된 부분집합 끼리는 서로 겹치는 원소가 없다.

예를 들어보자

ex)

S = 1,2,3,4

A = 1,2

B = 3,4

C = 2,3,4

D = 4

라고 하면

A, B는 S의 분할

A, C는 S의 분할 x (두 번째 조건 위배)

A, D는 S의 분할 x (첫 번째 조건 위배)

임을 알 수 있다.

 

이러한 disjoint set의 연산에는 3가지 연산이 있다.

• make set : 초기화 연산, x를 유일한 원소로 하는 새로운 set을 만듦
• union : x가 속한 set과 y가 속한 set을 합침
• find : x가 속한 set의 대표(루트)값을 반환

이들의 연산 메커니즘에 대해 설명을 이어 붙이자면,

일반적으로,

find 연산의 시간 복잡도는 disjoint set의 원소 수가 n일때 O(logn)이 된다. 

이유는 부모 노드를 반복적으로 역추적해 부모 노드를 찾기 때문이다.

3-4-5-2-1이라면

3의 루트 노드를 찾으려면 4, 5, 2, 1 순으로 추적을 해야 하기 때문이다.

 

이러한 find 연산을 더 효율적으로 하기 위해 path compression이라는 연산을 수행한다

출처 : 한다성 교수님 강의자료

path compression은 다음과 같이 모든 노드가 루트를 가리키도록 만드는 것이다.

S에는 부모 노드 인덱스 대신 루트 노드를 저장하게 된다.

 

이 것을 사용하면 find 연산의 시간 복잡도를 낮출 수 있음

 

그렇다면 union은 어떻게 수행하면 효과적일까?

임의의 두 disjoint set을 합칠 때는 원소 수가 적은 set을 많은 set의 sub tree로 합치는 것이 효율적이다 (Union by Rank). 다음 union 연산 때 반드시 find 연산을 수행해야 하는데 find 연산의 효율성을 높여주기 위함이다.

 

이러한 union by rank의 시간 복잡도는 O(1)이 된다.

 

union - find의 코드는 다음과 같다.

parent = {}
rank = {}

def make_set(v) : 
	parent[v] = v
	rank[v] = 0

## Find by path compression
def Find(v) : 
	if parent[v] != v : 
		parent[v] = Find(parent[v])
	return parent[v]

def Union(u,v) : 
	x, y = Find(u), Find(v)
	if x == y return
	if rank[x] > rank[y] : 
		parent[y] = x # union by rank
	elif rank[x] < rank[y] : 
		parent[x] = y # union by rank
	else : 
		parent[y] = x
		rank[x] += 1

 

 

path compression, 즉 경로 압축을 하기 전, union-find 알고리즘의 시간 복잡도는 O(logn)이지만 경로 압축을 하게 되면 시간 복잡도는 A(n), 즉 아커만 함수의 시간 복잡도를 갖는다

 

아커만 함수에서 N이 2^65536일 때, 아커만 함수의 값은 5가 되므로 상수의 시간 복잡도를 가진다. 즉, 매우 빠른 알고리즘이다.