[Algorithm] 유니온 파인드(Union-Find) 알고리즘

 

유니온 파인드(Union-Find) 알고리즘

 

 

분리집합 (서로소 집합, Disjoint Set)의 합집합(Union)과 같은 집합에 속하는지 여부(Find) 를 확인하는 알고리즘.

 

예시는 정수들의 집합으로하겠다. 

 

1~9 까지 정수 9개가 각각 하나의 집합이라고 하자.

 

{1}, {2}, {3} ,{4}, {5}, {6}, {7}, {8}, {9}

 

각 정수가 하나의 노드라고 하고, 그래프라고 한다면 초기 상태는 각각 부모노드가 자기 자신인 구조로 설정한다.

 

이것을 프로그래밍적으로 표현한다면 2차원 배열로 다음과 같이 표현할 수 있다.

 

Node	1	2	3	4	5	6	7	8	9
Parent	1	2	3	4	5	6	7	9	9

 

여기서 집합 {1} 과 {2} 를 합친다고 하면 다음과 같이 공통의 부모를 두도록 하면 된다.

(1번 노드와 2번 노드의 연결)

 

공통 부모를 설정할때는 기준이 필요한데, 일반적으로 더 작은 노드 번호를 부모로 한다. (Union)

 

Node	1	2	3	4	5	6	7	8	9
Parent	1	1	3	4	5	6	7	9	9

 

1과 2는 공통 부모로 1을 가지므로 

 

집합은 {1,2}, {3}, {4}, {5}, {6}, {7}, {8}, {9} 로 표현이 가능하다.

즉 공통 부모를 가지는 것은 같은 집합에 속한다는 뜻(Find)

 

 

만약 아래와 같이 2번노드와 3번노드가 연결되어있다고 하자.

 

Node	1	2	3	4	5	6	7	8	9
Parent	1	1	2	4	5	6	7	9	9

 

3번 노드의 최종 부모는 재귀 호출을 통해 3->2->1로 확인 가능하다.

그러므로 여기선 1,2,3 이 모두 같은 집합에 속해있다.

 

 

따라서 최종 부모를 찾는 행위 (같은 집합에 속해있는지 확인하는 행위)는 재귀 호출로 가능하다. (getParent)

 

이제 각 함수를 구현해보면 다음과 같다.

 

 

구현(C++)

 

#include <cstdio>

int parent[10];

int getParent(int a) {
	for (; a != parent[a]; a = parent[a]);
	return a;
}

void Union(int a, int b) {	// 서로소 집합을 합침(부모를 같게)
	a = getParent(a);
	b = getParent(b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

bool Find(int a, int b) {	// 같은 집합에 있는지 확인(부모가 같은지)
	if (getParent(a) == getParent(b)) return 1;
	else return 0;
}