유니온-파인드(Union-Find), 서로소 집합(Disjoint Set)

Union Find와 Disjoint Set은 동일한 의미를 가지며, 여러 서로소 집합의 정보를 저장하고 있는 자료구조를 의미합니다.

 

트리 형태로 구현되며, 보통 자신의 root 노드를 집합을 구분하는 ID처럼 사용된다.

 

 

이 자료구조는 두 가지 연산을 지원한다.

1. find(p): p의 root 노드의 값을 가져옴

2. union(p, q): p와 q의 집합을 합친다.

(코드 구성 시에는 union이라는 예약어가 있어 merge로 대체)

 

맨 처음에는 모든 노드가 자기 스스로를 root 노드로 가지게 된다.

 

find 함수는 현재 자기의 parent 노드가 자신이면 자기를 반환하고, 아니면 자신의 parent 노드의 parent노드를 반환한다.

이러한 방식으로 자신의 root 노드를 찾게 된다.

 

union함수는 p, q의 root 노드를 찾아 하나의 root 노드를 다른 집합을 root 노드로 바꾸는 거다.

예를 들어, 아래와 같은 집합이 존재할 때,

 

union(2, 5)를 하게 되면 2의 root 노드인 1의 parent 노드를 5의 root 노드인 4로 바꾸게 된다.

물론 구현에 따라 반대의 경우가 될 수도 있다.

int parent[1000], size[1000]; 
void init()
{ 
	for (int i=0; i<1000; i++) 
    { 
    	parent[i] = i;
    } 
} 
int find(int p)
{
	if(parent[p] == p) 
		return p; 
	else 
		return find(parent[p]); 
} 
void merge(int p, int q)
{ 
	p = find(p); 
	q = find(q); 
	parent[p] = q; 
}

 

하지만 위와 같이 연산을 하다보면 

위와 같은 상황에서는 find를 하는데 상당히 오랜 시간 걸린다. 

 

항상 모든 노드가 스스로의 root 노드를 가리킨다면 시간이 상당히 단축될 것이다!

 

그래서 find 연산을 할 때마다 이를 수정하면 속도가 상당히 개선된다.

 

int parent[1000], size[1000]; 
void init()
{ 
	for (int i=0; i<1000; i++) 
    { 
    	parent[i] = i;
    } 
} 
int find(int p)
{
	if(parent[p] == p) 
		return p; 
	else 
		return parent[p] = find(parent[p]); 
} 
void merge(int p, int q)
{ 
	p = find(p); 
	q = find(q); 
	parent[p] = q; 
}