[Algorithm] 유니온 파인드 (Union-Find) : Disjoint-set 표현

인트로

Union-Find 알고리즘은 서로소 집합*(Disjoint-set)을 표현하는 그래프 알고리즘으로 임의의 두 노드(원소)가 서로 같은 그래프(집합)에 속하는지 판별하는 알고리즘이다. 여기엔 핵심이 되는 두 가지 연산이 존재한다.

Union : 원소 x가 포함된 집합과 원소 y가 포함된 집합을 하나로 합치는 연산

Find : 원소 x가 포함된 집합을 반환하는 연산

 

참고로 Union-Find 알고리즘은 최소 신장 트리(MST)를 구하는 크루스칼 알고리즘에 사용된다.

서로소 집합 (Disjoint-set)이란?
공통 원소가 없는 두 집합을 서로소 집합이라 한다.

A = { 1, 2 ,3 } B = { 5, 7, 9 }  집합 A와 B는 서로소 집합이다.
A = { 3, 5 ,7 } B = { 7, 9, 11 } 집합 A와 B는 서로소 집합이 아니다.

Union-Find : 이해하기

다음과 같이 노드(원소)가 있다고 가정해 보자. 현재 각각의 노드는 자기 자신만을 포함하는 집합의 유일한 원소이다. 쉽게 말해 5개의 노드 모두 서로 다른 그래프(집합)에 있다고 생각하자.

나아가 위 상태를 표현할 아래와 같은 자료구조가 있다고 상상해 보자.

 

1) 이때 노드 1과 노드 2를 합치는 Union(1, 2) 연산을 수행하게 되면 다음과 같이 그래프가 형성되며 자료구조에 변화가 생긴다.

 

2) 여기서 노드 2와 노드 3를 합치는 Union(2, 3) 연산을 한 번더 수행하면 노드 1, 2, 3이 하나의 집합이 된다.

 

2) 마지막으로 노드 4와 노드 5를 합치는 Union(4, 5) 연산을 수행하면 노드 4와 노드 5가 하나의 집합이 된다.

 

Union-Find : 코드

#include <iostream>
using namespace std;

int unf[101];

int Find(int a)
{
	if (a == unf[a])
		return a;
	else
		return Find(unf[a]);
}

void Union(int a, int b)
{
	a = Find(a);
	b = Find(b);

	if (a != b)
		unf[b] = a;
}

bool IsUnion(int a, int b)
{
	if (Find(a) == Find(b))
		return true;
	else
		return false;
}

int main()
{
	for (int i = 1; i <= 100; i++)
		unf[i] = i;

	Union(1, 2);
	Union(2, 3);
	Union(4, 5);

	cout << "노드 번호 : ";
	for (int i = 1; i <= 5; i++)
	{
		cout << i << " ";
	} cout << endl;

	cout << "집합 번호 : ";
	for (int i = 1; i <= 5; i++)
	{
		cout << unf[i] << " ";
	} cout << endl;

	cout << "1과 2는 같은 집합? : " << IsUnion(1, 2) << endl;
	cout << "3과 4는 같은 집합? : " << IsUnion(3, 4) << endl;
}