유니온 파인드(Union-Find, Disjoint Set)

유니온 파인드란?

이름 그대로 Union 연산과 Find 연산을 지원하는 자료구조입니다.

상호 배타적(중복되지 않은) 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는데 사용합니다.

유니온 파인드 연산

일반적으로 트리 형태의 자료구조로 표현하며 아래 3가지 연산을 사용합니다.

 

- 초기화: N개의 원소가 각각 자기자신을  루토 노드로 설정합니다.

- UNION 연산: 두 원소 a, b가 주어질때, 로트 노드를 동일하게 설정하여 이들이 속한 두 집합을 합칩니다.

- FIND 연산: 원소 a에 대한 로트 노드를 재귀함수로 탐색을 합니다.

출처 : https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

유니온 파인드 구현

아래와 같이 초기화, UNION, FIND 함수를 구현할 수 있습니다.

const int MAX_SIZE = 1000000;
int root[MAX_SIZE];
// 초기화: 각 원소의 root 노드를 자기자신으로 설정
for (int i = 0; i < MAX_SIZE; i++)
	root[i] = i;
// FIND 연산
int FIND(int n)
{
	//부모노드가 자기자신이면 그 값을 반환
	if (n == root[n]) return n;
	//그외의 경우 재귀함수를 통한 부모노드 계산
	return root[n] = FIND(root[n]);
}
// UNION 연산
void UNION(int a, int b)
{
	a = FIND(a);
	b = FIND(b);
	// root 노드가 서로 같으면 바로 종료
	if (a == b) return;
	// a의 root 노드값을 갱신
	root[a] = b;
}

유니온 파인드 구현 (최적화 로직 추가)

트리 구조가 완전 비대칭인 최악의 경우 연결 리스트 형태를 이루게 되며, 알고리즘의 효율성이 떨어지게 됩니다.

이를 보안하기 위해 2개의 트리를 합칠때, 항상 높이가 더 낮은 트리를 높은 트리 밑에 넣으므로써 해결이 가능합니다. 

const int MAX_SIZE = 1000000;
int root[MAX_SIZE];
int height[MAX_SIZE]; // 트리의 높이를 기록
// 초기화
for (int i = 0; i < MAX_SIZE; i++)
{
	root[i] = i; //각 원소의 root 노드를 자기자신으로 설정
	height[i] = 0; //트리의 높이를 0으로 초기화
}
// FIND 연산(변화 없음)
int FIND(int n)
{
	//부모노드가 자기자신이면 그 값을 반환
	if (n == root[n]) return n;
	//그외의 경우 재귀함수를 통한 부모노드 계산
	return root[n] = FIND(root[n]);
}
// UNION 연산
void UNION(int a, int b)
{
	a = FIND(a);
	b = FIND(b);
	// root 노드가 서로 같으면 바로 종료
	if (a == b) return;
	// a트리의 높이가 b트리가 낮은 경우 a의 root 값을 변경
	if (height[a] < height[b]) parent[a] = b;
	// 그 외의 경우에는 b의 root 값을 변경
	else
	{
		parent[b] = a;
		//두 원소 트리의 높이가 같은경우 추가되는 원소의 높이를 1 증가
		if (height[a] == height[b]) height[a]++;
	}
}

유니온 파인드 알고리즘 예제

www.acmicpc.net/problem/1717

1717번: 집합의 표현

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int n, m;
int job;
int a, b;

const int MAX_SIZE = 1000000;
int parent[MAX_SIZE+1];
int height[MAX_SIZE+1];

int FIND(int n)
{
	//부모노드가 자기자신이면 그 값을 반환
	if (n == parent[n]) return n;
	//그외의 경우 재귀함수를 통한 부모노드 계산
	return parent[n] = FIND(parent[n]);
}

void UNION(int a, int b)
{
	a = FIND(a);
	b = FIND(b);

	if (a == b) return;

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

int main(int argc, char* argv[])
{
	scanf("%d %d", &n, &m);
	//초기화
	for (int i = 0; i <= n; i++)
	{
		parent[i] = i;
		height[i] = 0;
	}

	for (int i = 0; i < m; i++)
	{
		scanf("%d %d %d", &job, &a, &b);
		if (job == 0)
			UNION(a, b);
		else
		{
			if (FIND(a) == FIND(b))
				printf("YES\n");
			else
				printf("NO\n");
		}
	}

	return 0;
}