Union Find (Disjoint set)

Union Find 알고리즘은 여러개의 노드가 존재할 때 두 개의 노드를 선택하여 두 노드가 같은 그래프에 속하는지를 판별하는 알고리즘이다.

예를 들자면 이런 그래프가 있을 수 있다.

노드 1과 노드 4가 같은 그래프에 속한다는 것을 보고 판단하는 것은 간단하다.

하지만 컴퓨터는 이런 연결관계를 단번에 파악할 수 없다.

이를 해결하기 위해 DFS나 BFS를 수행하여 노드 1과 노드 4 사이의 연결관계를 확인할 수도 있겠지만, 단순히 같은 그룹에 속하는지 여부를 판단하기 위해서는 훨씬 편한 방법이 존재한다.

로직을 간단하게 설명하면 아래와 같다.

1. 두 노드 사이의 연결관계가 들어오면 두 노드에 대해 union 절차를 수행한다.
2. 두 노드 사이의 연결관계를 확인하려면 두 노드에 대해 find 절차를 수행한 뒤 이를 비교한다.

우선 union과 find가 무엇인지를 알아야 할 것이다.

Find 연산은 아래와 같이 구현할 수 있다.

int		find(int a)
{
	int		temp;
	
	if (array[a] == a) //만약 array[a]의 값이 자기 자신이라면 그대로 return 한다.
		return (a);
	temp = find(array[a]); // find를 이용하여 재귀적으로 탐색한 뒤 조상 노드를 찾는다.
	array[a] = temp; // array[a]에 이 값을 추가하여 연결관계를 간략화한다.
	return (temp);
}

이러한 절차를 한번 진행하고 나면 아래와 같이 array가 바뀌게 된다.

Union 연산은 이렇게 구현할 수 있다.

void	union(int a, int b)
{
	a = find(a);
	b = find(b);
	if (find(a) == find(b))
		return ;
	array[a] = b;
}

union 절차는 기본적으로 find 절차를 포함하고 있다.