[야매 알고리즘] Disjoint-set(Union-find)

야매 알고리즘?

알고리즘의 정확한 정의나 의미를 다루지 않고 핵심적인 작동 원리와 코드 예제를 정리하기 위한 시리즈입니다.

전부 짚고 넘어가면 좋겠지만 그럴 지식도 없고, 공부하는 것보다 정리하는데 더 많은 에너지와 시간을 소모할 것 같아서, 기억을 되살리기 위한 아카이브 정도로만 사용할 수 있게 간단하게 정리할 예정입니다.

 

개요

Disjoint-set: 서로 겹치지 않는 부분 집합들로 이루어진 데이터를 다루기 위한 자료구조.

union, find 연산으로 주어진 데이터를 disjoint-set으로 만들어 다룰  수 있다.

Disjoint-set은 forest 형태로 표현할 수 있는데, 같은 부분 집합에 있는 원소들이 하나의 tree를 이루는 형태이다.

Forest 형태로 표현한 disjoint-set

위 그림의 각 tree가 겹치지 않는 하나의 부분 집합을 의미한다. 

 

Find 연산은 특정 node가 포함된 tree의 root node를 반환한다. 위 그림에서 find(0)의 반환값은 7, find(6)의 반환값은 7, find(16)의 반환값은 16이다. tree의 root node는 유일하, find()의 결과가 같은 두 node는 같은 tree, 즉 동일한 부분 집합에 속해있다는 의미이다.

 

Union 연산은 두 겹치지 않는 부분집합을 하나의 부분집합으로 만든다. 위 그림에서는 두 tree를 하나로 합치는 것을 의미하는데, 한 tree의 root node를 다른 하나의 tree의 root node의 child node로 만드는 방식을 사용한다.

예를 들어 union(1, 10)은 아래 그림과 같다.

Union(1, 10)의 결과

Node 1이 속한 tree의 root node는 7이고, node 10이 속한 tree의 root node는 9이므로 이런 결과가 나온다.

 

이런 tree 형태의 구조는, 자기 자신의 parent node를 저장하고 있는 배열로 표현이 가능하다.

 

 

최적화

Find를 할 때 약간의 트릭을 사용하면 find와 union 연산의 속도를 높일 수 있다.

이것을 path compression이라고 하는데, find()의 반환값인 root node를, root node를 찾기 위해 거쳐갔던 node들의 parent로 기록해준다. 예를 들어서

위 그림에서 find(0)을 하면,

 

아래 그림처럼 된다. Node 0과 그 상위 node였던 1, 7의 parent를 root node인 9로 기록한 것이다. 이제 다시 한번 find(0)을 하면 연산 속도가 O(1)이 됨을 알 수 있다. find(1), find(2), find(3)의 경우에도 연산속도가 더 빨라졌음을 알 수 있다.

Union을 할 때도 find 연산을 사용해야 하기 때문에 disjoint-set을 조작하는 과정에서 자동으로 path compression을 통한 최적화가 일어남을 알 수 있다.

 

코드

class DisjointSet
{
	//parent[i]는 node i의 parent node를 의미함
	int[] parent;

	public DisjointSet(int N)
	{
		parent = new int[N + 1];
		//node i의 parent를 자기 자신으로 초기화
		for (int i = 1; i <= N; i++)
			parent[i] = i;
	}

	public void union(int e1, int e2)
	{
		int parent1 = find(e1);
		int parent2 = find(e2);
		parent[parent1] = parent2;
	}

	public int find(int e)
	{
		//root node에 도달했으면 반환
		if (parent[e] == e)
			return e;
		//path compression. 모든 상위 node의 parent를 root node로 바꿈.
		//tree의 height가 1이 된다.
		parent[e] = find(parent[e]);
		return parent[e];
	}
}