[Algorithm] Union & Find – Disjoint-set structure

Union & find 연산은 서로 다른 그룹을 하나의 그룹으로 합칠 때 사용한다. Minimum spanning tree를 만드는 Kruskal 알고리듬 등에서 사용한다.

어떤 A B C D E F G H의 8개의 항목들이 1~4까지의 그룹에 속해 있을 때, 각 항목의 그룹이 다음과 같이 있다고 하자.

{ A – 1, B – 1, C – 2, D – 2, E – 3, F – 3, G – 3, H – 4 }

여기서 각 항목이 가진 그룹만 보면 { 1, 1, 2, 2, 3, 3, 3, 4 } 와 같다.

언뜻 생각해보면, B 항목이 속한 그룹(1번 그룹)과 G 항목이 속한 그룹(3번 그룹)을 합쳐서 { 1, 1, 2, 2, 1, 1, 1, 4 } 와 같이 만든다고 하면, G가 속한 그룹(3번 그룹)을 찾아서 이 그룹인 모든 항목(E, F, G)을 찾아서 1번 그룹으로 바꿔주어야 하므로 모든 노드를 확인해서 3인 그룹이 있다면 1로 바꾸어야 한다. 이걸 모든 노드를 돌면서 확인하면서 바꾸지 않아도 할 수 있게 만드는 게 disjoint-set structure의 union & find 연산이다.

그룹을 합칠 때는, 둘 중 어느 하나를 parent로 만드는 tree 구조를 이용한다. 즉, 하나의 tree에 있는 모든 노드는 하나의 그룹이 된다. 이걸 다시 쓰면, 어떤 노드의 root 노드와 다른 어떤 노드의 root가 같다면, 같은 그룹이다.

n개의 항목이 있다면 다음과 같이 n개 항목에 대한 배열(parent)을 잡아 각각의 항목의 index로 그룹명을 잡는다(rank 배열은 모두 1로 하고, union 연산에서 설명한다).

void makeset(int parent[], int rank[], int n)
{
	int i;
	
	for (i = 0; i < n; i++) {
		parent[i] = i;
		rank[i] = 1;
	}
}

Find 연산은 어떤 항목이 속한 그룹 번호, 즉, tree에서의 가장 상위 노드, root 노드의 번호를 반환한다. Optimization을 위해 어떤 항목이 find 연산 도중에 parent를 거쳐서 root까지 도달한다면, 그 항목과 그 parent모두를 해당 노드의 parent만 찾으면 root가 되도록 parent를 root로 바꾸어준다. 예를 들어, { A, B, C, D, E, F, G, H }가 { 0, 0, 2, 2, 0, 4, 3, 3 }과 같이 있을 때의 그림은 다음 그림의 왼쪽 그림과 같다. 이 때, F 항목에 대해 Find 연산을 하면 root 까지 가는 과정 중에 있는 노드들을 모두 parent가 root가 되도록 다음 그림의 오른쪽 그림과 같이 바꾼다. 이로써 parent 노드들 및 자신 중 어떤 노드가 어떤 그룹에 속하는지를 나중에 찾을 때(root까지 갈 때), 바로 찾아갈 수 있도록 한다.

int Find(int parent[], int x)
{
	if (x != parent[x])
		parent[x] = find(parent, parent[x]);

	return parent[x];
}

Union 연산은 두 항목의 root를 같게 만들어 두 항목이 속한 두 그룹을 하나의 그룹으로 합친다. 다시 쓰면, 자신들의 root를 찾아, 이 root 중 한 노드를 다른 root노드의 parent로 만들어 하나의 root로 만든다. 이 과정에서 각각의 항목이 find 연산을 하게 되는데, 이 때, 위에서와 같이 각각의 root까지 찾아가면서 거치는 모든 parent들도 모두 각각의 root를 바로 위 parent로 갖게 만들어 tree의 깊이를 낮춘다. Tree의 깊이가 깊어지면 자신의 그룹이 어떤 것인지를 아는데(root까지 찾아가는데) 시간이 오래 걸리므로, tree의 깊이를 깊게 하지 않기 위해서 find에서 깊이를 낮추는 것 외에 union 연산을 할 때, rank를 이용한다. 두 root 노드의 rank를 비교해 두 root 노드 중 rank가 높은 노드가 새로운 root가 된다. 또한, rank는 어떤 노드가 자신과 rank가 같은 다른 노드의 parent가 되면 1씩 증가한다. 따라서 rank 값은 자신의 sub tree가 최대로 깊이가 깊어졌을 때 rank + 1이 된다. find 연산을 거치면 깊이가 낮아지지만, rank가 증가한 후, root부터 어떤 leap node까지의 모든 노드가 한번도 find를 수행하지 않았다면, 최악의 경우 rank 깊이의 노드가 존재한다. 하지만, 서로 다른 rank의 두 root 가 합쳐진다 rank가 낮은 root노드의 tree는 항상 rank가 더 높은 tree의 sub tree가 된다. 이는 항상 최대 깊이를 rank 이하로 보장한다. 위의 예에서 F와 H의 그룹끼리 합친다고 하면 다음 그림과 같이 된다. 빨간색으로 표시한 값은 rank 값이다.

int Union(int parent[], int rank[], int x, int y)
{
	int rootX = find(parent, x);
	int rootY = find(parent, y);

	if (rootX == rootY)
		return 0;

	if (rank[rootX] < rank[rootY]) {
		parent[rootX] = rootY;
	} else if (rank[rootX] > rank[rootY]) {
		parent[rootY] = rootX;
	} else {
		parent[rootX] = rootY;
		rank[rootY]++;
	}
	
	return 1;
}

쓰고나니 주저리주저리 너무 길다.