[알고리즘] 합집합 찾기 알고리즘 (Union-Find)

합집합 찾기 알고리즘 (Union-Find)

서로소 집합(Disjoint-Set)이라고도 불리는 유니온 파인드는 서로 아무런 연결성도 없는 두 원소를 선택하여 그것들이 서로 같은 집합 내에 연결되어 있는 지 연결성을 확인하는 알고리즘입니다. 

 

알고리즘 원리

위와 같이 6개의 아무런 연결성 없는 원소들이 존재할 때 각각의 원소들은 자기 자신의 집합에 속해있습니다. 원소 1은 집합 1에 속해있으며 원소 4는 집합 4에 속해있는 것입니다.

원소 1과 2를 연결하게 되면 이 둘을 Union 한 것이며 일반적으로 값이 더 작은 쪽으로 집합을 합치게 됩니다. 즉 원소 1과 2는 모두 집합 1에 속하게 되는 것입니다.

위 원리대로 볼 때 원소 2와 3을 연결하게 되면 원소 3은 집합 2에 속해야 할 것입니다. 하지만 원소 2는 집합 1에 속해있기 때문에 결과적으로 원소 3은 집합 1에 속하게됩니다. 원소 3은 3과 연결된 원소 2가 속한 집합을 찾아 재귀적으로 Union을 다시 실행하여 결국 집합 1에 속하게 되는 것입니다.

 

이로써 원소 1, 2, 3은 모두 집합 1에 속하는 그래프가 된 것이며 원소 4, 5, 6 역시 위 과정을 실행하면 모두 집합 4에 속하는 그래프가 될 것입니다. 또한 집합 1과 집합 4의 어떤 원소든지 연결이 된다면 모든 원소들이 집합 1에 속하게 됩니다. 여기까지가 Union 과정이며 FInd는 두 원소가 동일한 집합 내에 속해있는 지를 찾아내는 알고리즘입니다.

 

알고리즘 구현

// Algorithm Analysis
// 합집합 찾기 (Union-Find)

#include <stdio.h>

// 속한 집합 찾기
int getSet(int set[], int x) {
	if (set[x] == x) return x;
	return set[x] = getSet(set, set[x]);
}

// 두 집합 합치기
void unionSet(int set[], int a, int b) {
	a = getSet(set, a);
	b = getSet(set, b);
	if (a < b)
		set[b] = a;
	else
		set[a] = b;
}

// 동일한 집합 내에 속해있는지 확인
int find(int set[], int a, int b) {
	a = getSet(set, a);
	b = getSet(set, b);
	if (a == b) return 1;
	return 0;
}

int main() {
	int set[7];
	for (int i = 1; i <= 6; i++) {
		set[i] = i;
	}
	// 원소 1, 2, 3 연결 | 원소 4, 5, 6 연결
	unionSet(set, 1, 2);
	unionSet(set, 2, 3);
	unionSet(set, 4, 5);
	unionSet(set, 5, 6);
	
	// 연결성 확인
	printf("1과 4가 같은 집합 내에 있는가? : %d\n", find(set, 1, 4)); // 0 (false)
	printf("원소 6이 속한 집합은? : 집합 %d\n", getSet(set, 6)); // 집합 4
	unionSet(set, 1, 4); // 원소 1과 4 연결
	printf("1과 4가 같은 집합 내에 있는가? : %d\n", find(set, 1, 4)); // 1 (true)
	printf("원소 6이 속한 집합은? : 집합 %d\n", getSet(set, 6)); // 집합 1

	return 0;
}

 

유니온 파인드 알고리즘은 이후의 고급 알고리즘 및 크루스칼 알고리즘(Kruskal Algorithm)에서 원소 간의 연결 여부를 판단하는 데 사용되는 알고리즘이므로 반드시 이해하고 넘어가셔야 합니다.

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.