★ Union-Find 합집합 찾기

Union-find는 대표적인 그래프 알고리즘이다. 바로 '합집합 찾기'라는 의미를 가진 알고리즘.

 

서로소 집합(Disjoint-set) 알고리즘 이라고도 불린다.

 

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

 

처음에는 자기 자신이 부모 노드로 되어있는 상태이다.

만일 1과 2과 연결되었다고 생각해보자. 그렇게 되면 2의 부모 인덱스에는 1이 들어간다.

 

부모를 합칠 때에는 일반적으로 더 작은 값 쪽으로 합친다.

 

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

 

이번에는 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이 되는구나!'하고 파악할 수 있다.

 

#include <iostream>
using namespace std;

// 부모 노드를 찾는 함수
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() {
	int parent[11];
	
	for(int i = 0; i < 11; i++) {
		parent[i] = i;
	}
	
	unionParent(parent, 1, 2);
	unionParent(parent, 2, 3);
	unionParent(parent, 3, 4);
	unionParent(parent, 5, 6);
	unionParent(parent, 6, 7);
	unionParent(parent, 7, 8);
	
	cout << "1과 5는 연결되어있나여? " << findParent(parent, 1, 5) << endl;
	unionParent(parent, 2, 7);
	cout << "1과 5는 연결되어있나여? " << findParent(parent, 1, 5) << endl;
	
	return 0;
}

 

다른 정점들을 연결하여도 결국에는 서로 연결된다.