[C++] Union-Find

 

 

 

Union-Find 정의

 

유니온 파인드(Union-Find)는 여러 노드에 대해 특정 2개의 노드를 연결해 1개의 집합으로 묶는 처리를 의미한다. Union은 집합으로 묶기 기능, Find는 노드가 속한 집합 탐색 기능으로 구성된 알고리즘이다.

 

Union-Find의 처리 방식은 다음과 같다.

 

 

 

 

 

Union-Find 동작 원리

Union-Find 동작 원리는 아래와 같은 순서를 가진다.

 

 

모든 노드들에 대해 1차원 int 배열을 선언하여 자신의 index를 저장한다. 처음에는 모든 노드가 연결되어 있지 않기 때문에 각 노드가 대표 노드가 된다.

 

 

 

 

 

 

2개의 노드에 대해 각각의 대표 노드를 찾아 연결하는 Union 연산을 수행한다. Union(1, 4)의 경우, 4번 노드의 대표 노드를 1번 대표 노드로 변경해준다. 이때, 항상 대표 노드끼리 연결을 해야 한다. (Find 연산 수행)

 

 

 

 

 

 

여기서 Find 연산은 대표 노드를 찾기 위해 재귀적으로 탐색하게 된다.

바로 대표 노드(자신과 동일한 노드)가 나타날 때까지이다.

 

여기서 재귀적 탐색 때문에 시간 복잡도가 복잡해질 수 있다. 따라서 Find 연산은 탐색뿐만 아니라 거치는 모든 노드 값을 루트 노드 값으로 변경하는 작업을 추가로 수행한다. 그러면 이후 탐색에서 시간 복잡도를 최소화 할 수 있다. 이것을 경로 압축이라고 부른다.

 

 

 

 

 

Union-Find 코드

#include <iostream>

using namespace std;

int P[10000001];

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

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

	if (start != end)
	{
		if (start < end)
			P[end] = start;
		else
			P[start] = end;
	}
}