유니온-파인드 (Union-Find)

 유니온 파인드는 집합간의 합집합을 나타낼 때 사용하는 자료구조이다. A[] = { 0, 1, 2 }, B[] = { 1, 2, 3 } 이라고 하고, B 배열이 A 배열로 합쳐진다고 가정하면 union 연산을 수행한 후에는 A[] = { 0, 1, 2, 3 } 이 되는 것이다.

 

 유니온 파인드에서는 두 가지의 연산을 수행할 수 있는데, 한 집합의 대표를 리턴하는 find 와 두 집합을 합치는 union 연산이 있다. 초기 상태에는 한 원소가 하나의 집합이 되고, 그 원소가 그 집합의 대표가 된다. C++로 구현한 기본적인 유니온 파인드는 다음과 같다.

vector<int> parent;

void init(vector<int> p)
{
	for (int i = 0; i < parent.size(); i++)
	{
		parent[i] = i;
	}
}

int find(int x)
{
	if (parent[x] == x)
	{
		return x;
	}
	return find(parent[x]);
}

void union(int a, int b)
{
	int aRoot = find(a);
	int bRoot = find(b);

	if (aRoot == bRoot)
	{
		return;
	}
	
	parent[a] = b;
}

 가장 기본적인 유니온 파인드 구현이다. 하지만 이는 입력값이 커질수록 수행 시간이 많이 증가하게 된다. union 연산에서 원소가 적은 쪽으로 계속 합쳐질 경우 find 연산에서 수행되는 재귀 호출이 많아지기 때문이다. 이를 방지하기 위해서는 두 가지 최적화를 적용할 수 있다. 첫번째로는 find 연

산에서 재귀 호출된 값을 parent 배열에 저장한 뒤 리턴하는 것이다. 이렇게 하면 호출 트리가 불균형적으로 되는 것을 방지할 수 있다. 두번째로는 union 연산에서 항상 작은 루트값을 가진 집합에 합치는 것이다. 이렇게 하면 집합이 합쳐지면서 원소가 많은 쪽으로 합쳐지게 강제할 수 있다.

 

 이 두 최적화를 적용한 코드는 다음과 같다.

vector<int> parent;

void init(vector<int> p)
{
	for (int i = 0; i < p.size(); i++)
	{
		parent[i] = i;
	}
}

int find(int x)
{
	if (parent[x] == x)
	{
		return x;
	}
	return parent[x] = find(parent[x]);
}

void union(int a, int b)
{
	int aRoot = find(a);
	int bRoot = find(b);

	if (aRoot == bRoot)
	{
		return;
	}
	
	parent[max(aRoot, bRoot)] = min(aRoot, bRoot);
}

 참고로 함수명 union 은 C++에서 예약어이기 때문에 그대로 쓰면 오류가 난다.