[알고리즘/자료구조] 분리 집합( Disjoint Set (a.k.a Union & Find) ) 코드 구현 C++ , 집합 크기 구하기

 

분리 집합이란 교집합이 존재하지 않는 두개 이상의 집합을 뜻한다.

구분해야 하는 데이터 집합들을 다루는 알고리즘에서 사용할 수 있다.

분리집합에서는 자식 노드가 부모 노드를 가리키게 되어 있다. 보통 특정 집합의 대표 노드(루트)를 자식 노드들이 가리키고 있는 형태이다. 

 

분리집합 연산에는 두 가지가 있다.

 

1. Union(x,y)

합집합 연산이다.

두개의 집합을 합치기 위해서 각 두 집합의 대표(루트)노드를 찾고, A의 대표노드의 부모를 B의 대표 노드로 설정한다.

Union 연산

void Union(int x, int y) {
	int px = Find(x);
	int py = Find(y);
	if (px != py) {
		parent[px] = py;
		set_size[py] += set_size[px];
	}
}

합치려고 하는 각 원소가 속한 집합의 대표 노드를 Find함수로 찾아 부모노드를 바꿔준다. 

여기서 set_size는 각 집합의 대표 노드에 집합의 크기(원소 개수)를 저장한다.

(초기에 size배열은 모두 1으로, parent배열은 각 수를 저장한다. ex: parent[3]=3 , 어느 집합에도 속해있지 않을때는 자신으로 설정)

 

2. Find(x)

x가 속한 집합을 구한다. x에서부터 위로 올라가며 부모를 찾아서 리턴한다.

int Find(int x) {
	if (x == parent[x]) return x;
	return parent[x] = Find(parent[x]);
}

세번째 줄을 보면 단순히 x의 parent를 리턴하지 않는다. 

이렇게 하는 이유는 경로를 압축하기 위해서이다. 

만약 왼쪽 처럼 parent 관계를 저장한다면, 가장 밑에 노드에서 가장 위의 대표노드를 찾기 위해서 탐색을 오래 해야 하기 때문에 비효율적이다. 

 

오른쪽 처럼 저장하는게 훨씬 효율적으로 보인다. 

이를 위해 parent[x]를 리턴하면서 Find(parent[x]) 를 넣어준다.