[C++] 분리 집합( Disjoint Set )과 합집합 찾기( Union-Find ) 알고리즘

 

분리 집합( Disjoint Set )이란

분리 집합이란 전체 집합의 원소들을 교집합이 없도록 분할한 부분 집합들을 말합니다.

 

예를 들면, SNS에서 A란 사람과 친구 관계를 가진 사람들 집합과, 아무런 관계가 없는 사람들 집합으로 나누면, 이 집합들이 분리 집합입니다.

 

이 집합들을 가지고 하고자 하는 것은, 두 원소를 선택했을 때, 이 두 원소가 같은 집합에 속하는지, 그렇지 않은지를 알고 싶은 것입니다.

 

이를 해결하는 가장 간단한 방법은 각 원소에, 그 원소가 속한 집합의 이름을 적어놓는 것입니다.

 

원소가 속한 집합 표시

 

만약, 2와 5의 원소가 같은 집합 이름을 갖고 있다면, 두 원소는 같은 집합에 속해 있다는 것을 바로 알 수 있을 것입니다.

이 경우엔, 2와 5는 같은 집합에 속해 있지 않습니다.

 

그런데, 분리 집합을 가지고 한 가지 일을 더 해야 할 필요가 생겼습니다.

분리 집합들을 결합할 필요가 생긴 것입니다.

 

만약, 2와 5의 원소가 같은 집합에 속하지 않는다면, 5가 속한 집합 Y의 모든 원소를 2가 속한 집합 X로 이동시킬 필요가 생긴 것입니다.

이 일은 전체 집합의 크기가 작으면 별 문제가 되지 않습니다.

그러나, 그 크기가 무시하지 못할 정도가 되면 더 이상 간단한 문제는 아닙니다.

Y 이름을 기록한 모든 원소들을 찾아서, 원소에 적어둔 집합 이름을 X로 다 바꿔야 하기 때문입니다.

 

이 문제를 해결하기 위해 Union-Find 알고리즘이 등장했습니다.

 

합집합 찾기( Union-Find )

이 알고리즘은 배열 형식 데이터 구조 대신에, 트리 구조를 사용합니다.

원소가 속하는 집합 이름을 기록하는 대신에, 현재 집합에 먼저 속해있던 원소의 이름을 기록하는 방식입니다.

 

예를 들어, {1}, {2}, {4} 집합들이 있고, {1}에 {2}, {4} 집합을 결합하려면 다음과 같이 기록합니다.

 

합집합의 구조

 

이때, 루트( root )가 되는 원소는 자기 자신의 번호를 이름으로 적어서 루트 원소임을 표시합니다.

 

그러면, 이전 항목에서 단순히 집합 X와 집합 Y로 분리했던 방식을 다음과 같이 바꿀 수 있습니다.

(설명상, {5} 집합에 {3}, {6} 집합을 결합했다고 설정했습니다.)

 

배열 구조에서 트리 구조로 변환

 

이렇게 바꾸면, 이제 두 집합을 합하는 문제는 집합들의 크기와 상관없이 아주 간단해집니다.

집합 Y의 루트인 5를 집합 X의 루트인 1의 자식 노드로 연결만 하면 되기 때문입니다.

 

두 집합의 결합

 

게다가, 집합의 이름도 쉽게 구할 수 있습니다.

자식 노드로부터 부모 노드를 따라가다 보면, 루트에 도달하고, 그 루트에 집합 이름이 있기 때문입니다.

이제, 임의의 원소 두 개를 선택해서, 같은 집합에 속하는지 확인하는 문제도 해결되었습니다.

 

이 기능들을 코드로 바꾸면 다음과 같습니다.

#define SIZE 1000000	// 원소의 개수

int parent[SIZE+1];	// 각 원소의 부모 원소 기록

// 주어진 원소로부터, 루트 탐색
int Find_Root( int a){

    if ( parent[a] == a) 
        return a;

    return Find_Root( parent[a]);
}

// 두 집합 결합
void Union( int a, int b){
    
    int ra = Find_Root(a);
    int rb = Find_Root(b);

    if ( ra == rb)
        return;

    parent[ra] = rb;	// 한 집합의 루트를 다른 집합의 루트에 연결
}

 

그런데, Union 기능을 여러 번 수행하다 보면, 다음과 같은 트리가 생성될 수 있습니다.

 

편향된 트리

 

이렇게 편향된 트리에서 루트( root ) 노드를 찾는 것은 수행 시간을 무척 잡아먹는 일입니다.

따라서, 트리의 높이를 줄일 필요가 있습니다.

 

트리의 높이 조정

 

이제, 트리의 루트를 탐색하는 과정이 한 번의 수행만으로 완료됩니다.

 

위의 코드를 이에 따라 수정하면 다음과 같습니다.

int Find_Root( int a){

    if ( parent[a] == a) 
        return a;

    // 루트 탐색과 동시에 트리의 높이 조정 
    // a의 부모를 루트로 변경
    return parent[a] = Find_Root( parent[a]);
}

 

그리고, 최종 목표인 임의의 두 원소 a, b가 같은 집합에 속하는지를 알고 싶으면 다음과 같이 할 수 있습니다.

bool IsInSameSet( int a, int b){
    
    int ra = Find_Root(a);
    int rb = Find_Root(b);

    return ra == rb;
}