알고리즘

디스조인트-셋(disjoint-set) :: 마이구미

mygumi 2017. 11. 5. 17:27
반응형

이 글은 디스조인트-셋(disjoint-set) 자료구조를 다룬다.

유니온-파인드(union-find) 라고도 불리고, 머지-파인드-셋이라고도 불리는 자료구조이다.

위키백과 - 디스조인트-셋


디스조인트-셋은 해석하면 서로소 집합이라고 표현할 수 있다.

서로소 집합이란, 공통된 원소가 없는 집합으로써, 교집합이 공집합인 집합이라고 보면 된다.



디스조인트-셋을 활용하기 위해서는 다음과 같은 정의를 확실히 이해해야한다.


많은 상호 배타적 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조.


"상호 배타"와 "독립"을 혼동해서는 안된다.

독립은 집합으로 표현하면 다음과 같다.


A ∩ B = 0, A ∪ B = U


A와 B 사이에는 어떠한 관계도 존재하지 않다는 것을 알 수 있다.

상호 배타는 다음과 같다.


A ∩ B = 0, (A B) ⊂ C


A와 B는 공집합이지만, 둘은 하나의 집단(C)에 소속되어 있다는 의미가 된다.

상호 배타적 관계에서, A, B 사건이 존재한다면, A,B는 동시에 일어나지 않고, 둘 중 하나만 일어나야 한다.

독립적이라면, A, B 동시에 일어나도 상관이 없다.

이러한 의미는 다음 정의를 나타낼 수 있다.


두 사건이 상호 배타적이라는 것은 두 사건 중 한 사건이 일어날 확률[ P(A or B) ]이 두 사건이 각각 일어날 단순 확률의 합 [ P(A)+P(B) ]과 같다


문제를 접했을 때, 디스조인트-셋 문제인지 파악하기가 쉽지 않기 때문에 위와 같이 주어지는 사건에 대한 관계들을 정확히 이해해야한다.

구현은 쉽지만, 이해에 있어서는 쉽지 않은 자료구조이기 때문에, 본의아니게 설명이 길어졌다.


디스조인트-셋 구현에 있어, 크게 2가지로 볼 수 있다.

유니온(union), 파인드(find)가 존재한다.

부분 집합들은 트리로 표현할 수 있고, 파인드를 통해 루트 노드를 찾고, 유니온을 통해 트리를 합치게 된다.


  • 파인드(Find): 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다. 파인드는 일반적으로 어떤 원소가 속한 집합을 "대표" 하는 원소를 반환하는데, 이를 위하여 어떤 원소와 각 대표 원소들 간의 파인드 결과를 비교하여 같은 집합임을 판단한다.
  • 유니온(Union): 두 개의 집합을 하나의 집합으로 합친다.


초기에는 각 노드는 자기 자신을 루트 노드로 가지고 있다.


for (int i = 1; i <= n; i++) {
    parent[i] = i;
}

find를 통해 반환되는 값은 주로 그 집합을 대표하는 값이 된다.

이 값은 해당하는 트리(집합)에 대한 루트 노드라고 볼 수 있다.


public static int find(int u) {
    if (u == parent[u]) {
        return u;
    }
    return parent[u] = find(parent[u]); // 압축
    // return find(parent[u]) // 압축x
}


해당 노드는 루트 노드를 찾기 위해 부모값을 통해 계속해서 find 함수를 호출하게 된다.

빠른 속도를 위한 방법으로 find 과정 속에서 압축을 통해 모든 노드들의 루트 노드를 갱신하게 해준다.

다음과 같은 순서로 표현될 수 있다.


                  

                  


유니온 함수은 파인드를 통해 두 개의 트리의 루트 노드를 이용해서 하나의 트리로 합치게 된다.

유니온 함수는 파인드를 활용하기 때문에 파인드 함수를 정확히 이해해야한다.

4, 6을 유니온 함수를 통해 합치는 과정은 다음과 같이 표현할 수 있다.


public static void merge(int u, int v) {
    u = find(u);
    v = find(v);

    if (u == v) {
        return;
    }

    parent[u] = v;
}



각 트리의 루트 노드를 파인드를 통해 찾은 후 6을 가진 트리의 루트 노드를 4의 루트 노드로 갱신해준다.

응용 또는 이해를 위해서 level 과 같은 배열을 통해 트리의 레벨을 관리하면서 합쳐줄 수 있다. (관련 문제 풀이에서 참고바란다)

합쳐진 트리는 다음과 같이 표현할 수 있다.



이해를 돕기 위해 아래에 링크된 문제를 풀어보면 좋다. (위 코드만으로 해결가능하다)

그 후, 디스조인트-셋 카테고리에서 다른 문제들의 풀이를 참고하길 바란다.


디스조인트-셋은 최소 스패닝 트리 구현에서도 사용된다.

관련된 글은 추후에 다룰 예정이다.


집합의 표현 - https://www.acmicpc.net/problem/1717

관련 문제 - 디스조인트-셋 카테고리

Github - https://github.com/hotehrud/acmicpc/tree/master/disjoint-set

반응형