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

Union-Find ( 합집합 찾기) : 대표적인 그래프 알고리즘. 서로소 집합( Disjoint-Set) 알고리즘이라고도 한다.

여러 개의 노드가 존재할 때 두 개의 노드를 선택하여,

현재 두 노드가 같은 그래프에 속하는지 판별

-> Find와 Union 연산을 수행할 수 있다.

​

위와 같이 여러 개의 노드가 자유분방하게 존재하고 있다고 했을 때, 이들은 모두 연결되지 않고 각자 자신만을

집합의 원소로 가지고 있을 때 아래와 같이 표현할 수 있다. 모든 값은 자기 자신을 부모 노드로 가지고 있습니다.

이때,

위와 같이 1과 2가 연결되었을 때, 표로 표현하였을 때 아래의 표로 나타납니다.

노드 번호	1	2	3	4	5	6	7
부모 노드 번호	1	1	3	4	5	6	7

2번째 인덱스의 값에 ' 1 ' 이 들어갑니다. 즉, 노드를 합칠 때 일반적으로 더 작은 쪽의 값으로 합칩니다. 이를 합침(Union)합침(Union)이라고 합니다.

2와 3이 위와 같이 연결되었다면 어떻게 표현될까요?

노드 번호	1	2	3	4	5	6	7
부모 노드 번호	1	1	2	4	5	6	7

다음과 같이 연결됩니다. 근데 한 가지 의아한 점을 확인할 수 있습니다. 바로 ' 1 과 3이 연결되었는지는 어떻게 파악하는가? '입니다.입니다.

1과 3은 부모가 각각 1 과 2로 다르기 때문에 ' 부모 노드 ' 만 보고는 한 번에 파악할 수 없습니다.

​

이때 사용되는 것이 재귀 함수입니다. 입니다.

​

3의 부모를 찾기 위해서 먼저 3이 가리키고 있는 2를 찾습니다. 그럼 2의 부모가 1을 가리키고 있으므로 결과적으로

' 3은 1을 부모가 되는구나! '라고 파악할 수 있습니다.

-> 위와 같은 과정은 재귀적으로 수행될 때 가장 효과적이고 직관적으로 언어를 작성할 수 있습니다.

​

위 작업을 수행하면 결과적으로 ,

노드 번호	1	2	3	4	5	6	7
부모 노드 번호	1	1	1	4	5	6	7

노드 1, 2, 3의 부모가 모두 1이기 때문에 세 가지 노드는 모두 같은 그래프에 속한다고 할 수 있습니다.

​

이렇게 합침(Union) 연산이 수행, 탐색(Find) 연산은 두 개의 노드의 부모 노드를 확인하여 현재 같은 집합에 속하는지 확인하는 알고리즘

​

이것이 Union-Find의 전부입니다!

​

그럼 이것을 C 언어로 구현해 본다면!

 

#include <stdio.h>

// 부모 노드를 탐색합니다.
int getParent(int parent[], int x) {
	if (parent[x] == x) return x;
	else return parent[x] = getParent(parent, parent[x]);
}

// 각 부모 노드를 합칩니다.
int unionParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);

	if (a < b) parent[b] = a;
	else parent[a] = b;
}

// 같은 부모 노드를 가지는지 확인합니다.
int findParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);

	if (a == b) return 1;
	else return 0;
}

int main(void) {   
	int parent[8];

	for (int i = 1; i <= 7; i++) {
		parent[i] = i;
	}

	unionParent(parent, 1, 2);
	unionParent(parent, 2, 3);
	unionParent(parent, 3, 4);

	unionParent(parent, 5, 6);
	unionParent(parent, 6, 7);

	printf("%d\n", findParent(parent, 1, 3));    // 1
	printf("%d\n", findParent(parent, 1, 5));    // 0
}

이때 만약 위와 같은 예제에

unionParent(parent, 1, 5);

printf("%d\n", findParent(parent, 1, 5));

하면 과연 어떻게 나올까? 바로 공개하자면 1이 출력된다. 즉 1과 5는 부모 노드가 같다는 뜻이다. 이를 표로 표현하자면,

노드 번호	1	2	3	4	5	6	7
부모 노드 번호	1	1	1	1	1	5	5

위와 같이 나온다.

​

그렇다면! 3과 7을 연결하고 결과를 확인하면 어떻게 될까?

unionParent(parent, 3, 7);

printf("%d\n", findParent(parent, 1, 5));

마찬가지로 결과는 1이 출력된다. 이것의 표로 표현하면 마찬가지로 아래와 같이 나온다.

노드 번호	1	2	3	4	5	6	7
부모 노드 번호	1	1	1	1	1	5	5

unionParent(parent, 3, 7);

int unionParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);

	if (a < b) parent[b] = a;
	else parent[a] = b;
}

에서 a와 b의 값을 확인해보면 a : 1, b : 5 즉, parent [5] = 1;이 되기 때문이다.

이를 통해 5의 부모 노드 번호가 1이 되고

int findParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);

	if (a == b) return 1;
	else return 0;
}

를 통해 비교해보면, 각각 a : 1, b : 1 이 되기 때문에 a == b가 true가 나오므로 1이 출력되는 것이다.

​

자바로도 한번 구현해보자면!

import java.util.Arrays;

public class Study_Union_Find {

	public static int getParent(int[] parent, int x) {
		if(parent[x] == x) return x;
		else return getParent(parent,parent[x]);
	}
	
	public static void UnionParent(int[] parent,int x,int y) {
		int a = getParent(parent, x);
		int b = getParent(parent, y);
		
		if(a < b) parent[b] = a;
		else parent[a] = b;
	}
	
	public static boolean FindParent(int[] parent,int x, int y) {
		int a = getParent(parent, x);
		int b = getParent(parent, y);
		
		if(a == b) return true;
		else return false;
	}
	
	public static void main(String[] args) {
		int[] parent = new int[10];
		
		for(int i = 0; i < 10; i++) 
			parent[i] = i;
		
		UnionParent(parent, 0, 1);
		UnionParent(parent, 1, 2);
		UnionParent(parent, 2, 3);
		UnionParent(parent, 3, 4);
		
		UnionParent(parent, 5, 6);
		UnionParent(parent, 6, 7);
		UnionParent(parent, 7, 8);
		UnionParent(parent, 8, 9);
		
		System.out.println(FindParent(parent, 1, 6));
		
		UnionParent(parent, 4, 9);
		
		System.out.println(FindParent(parent, 1, 6));
		
		System.out.println(Arrays.toString(parent));
	}

}

이러한 Union-Find 알고리즘은 다른 고급 그래프 알고리즘의 베이스가 된다는 점에서 익혀야 하는 알고리즘이다.

다음에 포스팅하게 될 크루스칼 알고리즘(Kruskal Algorithm)은 이 Union-Find를 응용한 알고리즘이다.