Disjoint Set Data Structrue
서로소 집합을 관리하는 데 사용하는 자료구조이다.
집합을 나타내기 위해선, 각 집합마다 대표자(parent)를 사용한다.
이 p가 집합을 확인하고 추가하는데 사용하는 핵심 요소이다.
union-find
Find
parents[]에 각 노드의 parent(집합 대표자)를 저장한다.
이를 통해 어느 집합에 속해있는 지 확인할 수 있다.
int FindRecursive( int node )
{
// 대표자가 자신인 경우 끝.
return ( parents[node] == node ) ?
node : FindRecursive( parents[node] );
}
Union
void Union( int a, int b )
{
int pa = FindRecursive( a );
int pb = FindRecursive( b );
// 집합 a의 대표자를 b로 바꾼다. -> 집합 a의 모든 대표자는 pb로 변하게 된다.
parents[pa] = pb;
}Optimazation
위의 Union-Find 함수들로 disjoint set을 구현할 수 있다.
그러나, 여기에 몇 가지 최적화가 가능하다.
path compression
위 방식대로 Union을 여럿 거치다 보면 집합의 대표자를 찾기 위해 DFS를 깊게 들어가는 경우가 생길 수 있다.
대표자만 필요한데 중간 과정을 생략할수록 좋지 않을까?
아래 코드로 path compression이 가능하다.
int FindRecursive( int node )
{
// 대표자가 자신인 경우 끝.
return ( parents[node] == node ) ?
node : ( parents[node] = FindRecursive( parents[node] ) );
}
union by rank
위의 기본 Union은 특별한 조건 없이 두 집합을 합쳤다.
그러나 합치는 방식에따라 결과물의 path 길이가 달라질 수 있다.
예를 들어, 깊이 10짜리 집합 A와, 깊이 3짜리 집합 B가 있다고 해보자.
A가 B를 가리키도록 하면 완성된 집합은 깊이가 11이 된다.
반면 B가 A를 가리키게 하면 완성된 집합은 깊이가 여전히 10이다.
물론 path compression을 진행하긴 하지만, 애초부터 깊이를 최대한 덜 늘리면서 Union을 진행하면 더 빠를 것이다.
깊이를 rank라고 표현하면 아래와 같이 코드를 짤 수 있다.
void Union( int a, int b )
{
int pa = FindRecursive( a );
int pb = FindRecursive( b );
if ( rank[pa] < rank[pb] )
{
parents[pa] = pb;
}
else if ( rank[pa] > rank[pb] )
{
parents[pb] = pa;
}
else
{
parents[pb] = pa;
rank[pa]++;
}
}union by size
rank 대신 집합의 크기를 사용하여 위와 비슷한 아이디어로 풀 수 있다.
void unionBySize(int i, int j) {
// Find the representatives (or the root nodes) for
// the set that includes i
int irep = find(i);
// And do the same for the set that includes j
int jrep = find(j);
// Elements are in the same set, no need to unite
// anything.
if (irep == jrep)
return;
// Get the size of i’s tree
int isize = Size[irep];
// Get the size of j’s tree
int jsize = Size[jrep];
// If i’s size is less than j’s size
if (isize < jsize) {
// Then move i under j
Parent[irep] = jrep;
// Increment j's size by i's size
Size[jrep] += Size[irep];
}
// Else if j’s size is less than i’s size
else {
// Then move j under i
Parent[jrep] = irep;
// Increment i's size by j's size
Size[irep] += Size[jrep];
}
}