Disjoint Set (Union find)

Disjoint set이라고도 하고 union find라고도 하는 이 방법은 어느 두 집합을 합치고, 어느 두 요소가 같은 집합에 존재하는지 빠르게 알 수 있게 하는 방법이다.

Disjoint Set은 아래 두 연산을 구현한다.

• union(a,b)는 a가 속한 집합과 b가 속한 집합을 합치는 연산이다.
• find(a)는 a가 속한 집합을 반환하는 연산이다.

아래는 위 두 연산을 사용하였을 때의 예제이다.

• 1~5의 요소가 있다고 하자. 각 요소는 초기에 서로 다른 집합에 속한다.
  • (1), (2), (3), (4), (5)
• 1이 속한 집합과 2가 속한 집합을 합치자. : union(1,2)
  • 결과 : (1,2), (3), (4), (5)
  • find(1) == find(2)는 true이어야 한다.
  • find(2) == find(3)는 false 이어야 한다.
• 3이 속한 집합과 4가 속한 집합을 합치자. : union(3,4)
  • 결과 : (1,2), (3,4), (5)
  • find(3) == find(4)는 true이어야 한다.
  • find(2) == find(3)는 false 이어야 한다.
• 1이 속한 집합과 3이 속한 집합을 합치자. union(1,3)
  • 결과 : (1,2,3,4), (5)
  • find(1) == find(2)는 true이어야 한다.
  • find(2) == find(3)는 true이어야 한다.
  • find(4) == find(5)는 false이어야 한다.

간단한 구현

Disjoint Set은 트리 형태를 사용하여 구현할 수 있다. find에서는 트리의 루트 번호를 반환하도록 하고, union에서는 둘이 다른 트리에 속한 경우 한 트리를 다른 트리에 합쳐버리는 방법으로 구현하는 것이다.

만약 아래와 같은 집합들이 존재한다고 하자.

(1,2,3,4,5), (6,7,8), (9)

Disjoint Set을 구현하고 위 집합을 나타냈을 때 가능한 tree들은 union을 한 순서에 따라 다르다. 아래는 가능한 트리 중 하나의 예시이다.

// tree 1
2-1
L-3-4
L-5

// tree 2
6-7-8

// tree 3
9

find

만약 트리들이 위의 구조로 구성되었다면, find(4)는 무엇을 반환해야 할까?
4가 속한 트리의 루트는 2이다. 따라서 find(4) = 2 다.

9가 속한 트리의 루트는 9이기 때문에 find(9) = 9다.

union

union(a, b)은 두 트리를 합쳐버리는 방법으로 구현할 수 있다. 둘 중 하나 트리의 루트를 다른 트리의 child로 넣어주면 된다.

위 집합에서 union(6,3)을 수행할 때 단순히 6이 속한 트리의 루트를 3이 속한 트리의 루트의 child로 넣어주었다고 하자. 이후 트리들의 구조는 아래와 같다.

// tree 1 
2-1
L-3-4
L-5
L-6-7-8

// tree 2
9

code

코드로 짜보자.

#include <vector>

using namespace std;

class DisjointSet{
    vector<int> parent;

    public:

    DisjointSet(int n):parent(n){
        for(int i=0;i<n;++i) parent[i]=i;
    }

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

    // union
    void unio(int a,int b){
        a = find(a);
        b = find(b);

        // a가 속한 집합의 루트를 b가 속한 트리의 루트의 child로 만든다.
        parent[a] = b;
    }
};

문제점

만약 union(0,1),union(1,2),union(2,3),...,union(98,99)을 수행하였다면 생성되는 트리의 구조는 어떨까?

• union(0,1)을 수행했을 때

  
  1-0
  
  2
  
  3
  .
  .
  .
  99

• union(1,2)을 수행했을 때

  
  2-1-0
  
  3
  
  4
  
  .
  .
  .
  99

• union(2,3)을 수행했을 때

  
  3-2-1-0
  
  4
  
  5
  .
  .
  .
  99

• 이후 계속 union 연산을 하다 union(98,99) 까지 했을 떄

  
  99-98-97-...-2-1-0

트리가 그냥 긴 링크드리스트 마냥 한 줄로 길게 늘어져 있다. 이 경우 find를 수행하는 데에 O(N)가 걸린다. 만약 트리의 높이를 짧게 할 수 있다면 성능을 높일 수 있지 않을까?

개선된 구현

크게 두 가지 방법이 사용되는데, 하나는 find 할 때 지나가는 노드들의 parent를 모두 그 tree의 root로 바꿔버리는 Path Compression이고, 하나는 tree를 합칠 때 작은 트리가 큰 트리의 child로 합쳐지도록 하는 Union By Rank이다.

Path Compression, 경로 압축

find를 수행할 때 지나가게 되는 모든 노드의 parent를 그 tree의 root로 바꾸는 방법이다.

아래 예제는 어떤 트리에 Path Compression이 적용된 find(4)를 수행한 결과이다.

// 원래 tree
0-1
L-2-3-4-5
L-6-7

// Path Compression이 적용된 find(4) 수행 이후의 트리
0-1
L-2
L-3
L-4-5
L-6-7

find(4)를 수행하는 동안 재귀적으로 find(3),find(2),find(0)이 수행되었고, 루트인 0을 제외한 2,3,4번 노드의 parent는 0이 된 것을 볼 수 있다.

Path Compression이 적용된 find의 구현은 아래와 같다.

int find(int i){
    if(parent[i] == i) return i;
    return parent[i] = find(parent[i]); // set parent to root!
}

Union by rank

rank가 작은 tree를 rank가 큰 tree의 root의 child로 합쳐지도록 하는 방법이다.

Union By rank가 적용된 union의 구현은 아래와 같다.

// union
void unio(int a,int b){
    a = find(a);
    b = find(b);

    if(a==b) return; // 이미 같은 집합

    if(rank[a] < rank[b]){
        parent[a] = b; 
    }else{
        parent[b] = a;
        // 둘의 rank가 같다면 parent가 되는 
        // 노드가 존재하는 tree의 rank 증가
        if(rank[a]==rank[b]){ 
            ++rank[a];
        }
    }
}

코드구현

전체 구현은 아래와 같다.

#include <vector>

using namespace std;

class DisjointSet{
    vector<int> parent;
    vector<int> rank;

    public:

    DisjointSet(int n):parent(n),rank(n,0){
        for(int i=0;i<n;++i) parent[i]=i;
    }

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

    // union
    void unio(int a,int b){
        a = find(a);
        b = find(b);

        if(a==b) return; // 이미 같은 집합

        if(rank[a] < rank[b]){
            parent[a] = b; 
        }else{
            parent[b] = a;
            // 둘의 rank가 같다면 parent가 되는 
            // 노드가 존재하는 tree의 rank 증가
            if(rank[a]==rank[b]){ 
                ++rank[a];
            }
        }
    }
};

각 연산의 시간복잡도는 O(a(N))이다. 여기서 a()는 아커만 함수의 역함수이며, 거의 상수라고 봐도 된다.