Union-Find(합집합찾기)

 

Union-Find는 대표적인 그래프 알고리즘 입니다. 바로 '합집합 찾기'라는 이름의 알고리즘인데요. 서로소 집합(Disjoint-Set) 알고리즘이라고도 불리기도 합니다. 여러 개의 노드가 존재할때 두 노드가 같은 집합 안에 속했는지, 즉 연결이 되어있는지를 판별하는 알고리즘 입니다.

 

 

다음과 같은 노드셋이 있습니다. 모든 노드가 연결되어 있지 않고 자기 자신만을 집합의 원소로 가지고 있는 때입니다. 모든 값이 자기 자신을 가리키도록 만드는 겁니다. 

아래 표에선 첫번째 행은 '노드 번호'를 의미하고 두번째는 '부모 노드 번호'를 의미합니다. 즉, 자기 자신이 어떤 부모에게 포함되어 있는지를 의미합니다. 어차피 한 노드에만 연결되어 있으면 다른 노드에도 연결되어져 있게 되는거니깐요. 여기서 부모노드는 값이 더 작은 값으로 정했습니다. 

1	2	3	4	5	6	7
1	2	3	4	5	6	7

 

1과 2를 연결해보겠습니다.

이 그림에서 표는 이렇게 됩니다. 2의 부모가 1이라는 의미입니다. 이런걸 합침(Union)이라고 합니다. 

1	2	3	4	5	6	7
1	1	3	4	5	6	7

 

이 그림에서 표는 이렇게 됩니다. 3의 부모가 2이라는 의미입니다.

근데 문제가 생깁니다. 이렇게 되면 '1과 3이 연결되어있나?' 를 파악할 수 없게 됩니다. 어떻게 해야할까요

1	2	3	4	5	6	7
1	1	2	4	5	6	7

3의 부모노드인 2의 부모노드가 존재하는지 찾아야합니다. 이렇게 재귀적으로 나의 부모노드의 부모노드가 존재하는지 파악해서 나의 부모노드를 바꿔주는 겁니다. 재귀적으로 수행하면 더욱 직관적이고 효과적으로 구현을 할 수 있습니다. 그렇게 Union 연산이 다 수행되고 나면 다음과 같이 표가 구성됩니다.

1	2	3	4	5	6	7
1	1	1	4	5	6	7

노드 1, 2, 3 의 부모노드가 같기 때문에 같은 그래프에 속했음을 알 수 있습니다. Find 알고리즘은 두개의 노드의 부모노드를 확인하여 현재 같은 집합에 속해있는지 확인하는 알고리즘입니다. 

한번 구현을 해보도록 하겠습니다.  

 

#include <stdio.h>

// 부모 노드를 찾는 함수 
int getParent(int parent[], int x){
	if(parent[x]==x) return x; //부모노드가 없을때
	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;
	return 0;
} 

int main(void){
	int parent[11];
	//자기 자신이 부모가 되게 초기화 
	for(int i = 1; i <= 10;i++ ){
		parent[i] = i;
	}
	unionParent(parent,1,2); //1과 2을 연결 
	unionParent(parent,2,3); //2과 3을 연결 
	unionParent(parent,3,5); //3과 5을 연결 
	unionParent(parent,4,6); //4과 6을 연결 
	unionParent(parent,6,7); //6과 7을 연결 

	
	printf("1과 4는 연결되어 있나요? %d\n",findParent(parent,1,4));
	unionParent(parent,1,4);
	printf("1과 4는 연결되어 있나요? %d\n",findParent(parent,1,4));
}

이렇게 구현을 하고 난 그래프의 모습을 아래와 같습니다. (마지막 1,4 UnionParent 를 실행하기 전)

1	2	3	4	5	6	7
1	1	1	4	1	4	4

여기서 1과 4의 부모노드가 동일하지 않기 때문에 둘은 같은 그래프에 속해있지 않음을 알 수 있습니다.

그래서 위의 예처럼 1과 4를 연결해주면 True가 반환이 됩니다. 

물론 1과 4뿐만이 아니라 1과 6, 2와 4, 5와 7을 연결해도 True가 반환이 됩니다. 

 

오늘은 합집합 찾기, Union-Find를 배워보았는데요. 크루스칼 알고리즘과 같은 고급 알고리즘 등에 쓰이는 개념이기 때문에 꼭 알아두어야합니다. 

 

※이 글은 나동빈님의 포스팅 복습용입니다.※

https://blog.naver.com/ndb796/221230967614

17. Union-Find(합집합 찾기)