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

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

---

대표적인 그래프 알고리즘이며 서로소 집합(Disjoint-Set) 알고리즘이라고도 부른다. 여러개의 노드가 존재할 때 두개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판변하는 알고리즘이다.

숫자들을 설정하고 깊이 우선 탐색하는 프로그램을 작성하자!

부모를 합칠 때 일반적으로 더 작은 값으로 합치며 이것을 합침(Union)이라고 하며 노드를 선택해서 그 노드가 같은 합침에 속해있는지를 찾는 알고리즘이다.

소스코드 구현 (C++)

#include <iostream>

using namespace std;
//부모 찾기
int GetParent(int parent[], int x)
{
	if (parent[x] == x) return x;

	return parent[x] = GetParent(parent, parent[x]);
}
//합치기
void 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;
}
//찾는 알고리즘
bool FindParent(int parent[], int a, int b)
{
	a = GetParent(parent, a);
	b = GetParent(parent, b);

	return a == b ? true : false;
}

int main()
{
	int p[10];
	for (int i = 0; i < 10; i++)
	{
		p[i] = i;
	}

	UnionParent(p, 1, 2);
	UnionParent(p, 2, 3);
	UnionParent(p, 3, 4);

	UnionParent(p, 5, 6);
	UnionParent(p, 6, 7);
	UnionParent(p, 7, 8);

	cout << "1과 4는 연결되어 있는가? : " << FindParent(p, 1, 4) << endl;

	cout << "3과 5는 연결되어 있는가? : " << FindParent(p, 3, 5) << endl;

	cout << "6과 8는 연결되어 있는가? : " << FindParent(p, 6, 8) << endl;

	cout << "1과 9는 연결되어 있는가? : " << FindParent(p, 1, 9) << endl;

	cout << "8과 9는 연결되어 있는가? : " << FindParent(p, 8, 9) << endl;


	return 0;
}

출력 결과

---

합집합 찾기 알고리즘은 다른 고급 그래프 알고리즘의 기본이 되기 때문에 숙지를 해야한다. 대표적으로 크루스칼 알고리즘이 있다.