[트리] Tree 8: Disjoint Set 상호 배타적 집합, 유니온-파인드

1. 상호 배타적 집합

 

상호 배타적 집합을 표현할 때 유니온-파인드(union-find) 자료구조를 쓴다.

 

이 자료구조는 독특한 트리이다.

 

 

전체 집합을 공통 원소가 없는 여러 개의 부분 집합으로 쪼개어 나누어진 원소들(상호배타적인 부분 집합들)

에 대한 정보를 저장하고, 조작하는 자료구조가 유니온-파인드 자료구조이다.

 

이 자료구조의 핵심 연산은 다음과 같다.

 

- 초기화: n 개의 원소가 있을 때 자기자신으로만 이루어진 집합들.

- 합치기(union): 두 원소 a, b가 있을때 이들이 속한 두 집합을 하나로 합침

- 찾기(find): 어떤 원소 a가 주어질때 이 원소가 속한 집합을 찾는다.

 

 

 

2. 배열을 사용하여 상호 배타적 집합 표현하기

 

1차원 배열 하나를 이용하여 표현한다

 

belongsTo[i] = i번 원소가 속하는 집합의 번호

 

- 초기화: belongsTo[i] = i => 크기가 1인 n개의 집합

- 찾기: 인덱스 접근 => 상수시간

- 합치기: 모든 원소를 순회하면서 한쪽 집합에 속한 원소들을 다른 쪽 집합으로 이동. O(N)의 시간이 걸림

 

3. 트리를 이용한 상호 배타적 집합 표현

 

한 집합에 속하는 원소들을 하나의 트리로 묶어서 표현한다.

 

상호 배터적 집합: 트리들의 집합

 

두 원소가 같은 트리에 속해있는지 판단: 루트를 찾아 같은지 비교

 

루트: 각 집합의 대표

 

찾기연산: 주어진 원소가 포함된 트리의 루트를 찾는 연산 => 모든 자식 노드가 부모에 대한 포인터를 가지고 있어야함.

              반면 부모->자식으로 이동하는 경우는 없기 때문에 자식으로가는 포인터는 필요없음.

 

합치기 연산: 각 트리의 루트를 찾은 후 하나를 다른쪽의 자손으로 이동

 

 

두 연산 모두 트리의 높이에 시간 복잡도는 지배된다, 그러므로 O(n)의 시간 복잡도를 가진다.

 

struct NaiveDisjointSet {
    vector<int> parent;
    NaiveDisjointSet(int n) : parent(n) {
        for(int i = 0; i < n; ++i) 
            parent[i] = i;
    }
    int find(int u) const {
        if(u == parent[u]) return u;
        return find(parent[u]);
    }
    void merge(int u, int v) {
        u = find(u); v = find(v);
        if(u == v) return;
        parent[u] = v;
    }
};

 

4. 최적화된 상호 배타적 집합(Union-by-Rank)

 

트리를 이용하여 표현하게 되면 루트의 정보만 바꾸면 되기 때문에 배열로 표현한 것 보다 효율적이다

 

하지만 연산 순서에 따라 트리의 균형이 무너져 최악의 경우 연결 리스트 형태가되어 

모든 연산이 O(n)의 시간 복잡도를 가지게 된다.

 

이런 상황을 방지하기 위해  두개의 트리 중 낮은 트리를 더 높은 트리에 합침으로써

어느 정도 균형을 유지한다.( 중간그림이 오른쪽 그림보다 높이가 낮다.)

 

struct OptimizedDisjointSet {
    vector<int> parent, rank;
    OptimizedDisjointSet(int n) : parent(n), rank(n, 1) {
        for(int i = 0; i < n; i++) 
            parent[i] = i;
    }
    int find(int u) {
        if( u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
    void merge(int u, int v) {
        u = find(u); v = find(v);
        if(u == v) return;
        if(rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if(rank[u] == rank[v]) rank[v]++;
    }
};

 

높이 h인 트리가 생기기 위해서는 높이 h-1인 두개의 트리가 합쳐져야한다.

즉 높이가 1 씩 증가하려면 필요한 원소가 두배씩은 필요하다는 것 이다.

따라서 높이는 노드의 수의 로그에 비례하며 모든 연산은 O(lgn)이 된다.

 

경로 압축 최적화(path compression)

 

한번 루트를 찾아낸 후 다음 번에도 호출 되었을 때 바로 접근 할 수 있는 최적화이다.

 

위의 코드 처럼 찾기 연산을 할때 지나가는 원소들 모두 루트에 연결 시키는 것이다.

 

이를 통해 find연산을 여러번 실행했을 때 

실행마다 수행시간이 변하기 때문에 분할 상환 분석을 이용해서 수행시간을 계산해야한다.

 

find 와 merge 를 아주 많이 수행했을 때

O(a(n))의 평균시간이 걸린다고 한다.

이것은 모든 크기 n에 대하여 4이하의 값이라는 결과가 나온다고한다.

따라서 두 연산은 모든 입력에서 상수시간이 걸린다고 본다.

 

(a(n)은 애커만 함수를 이용해 정의되는 함수이다.)

(애커만 함수는 계산 가능성 이론을 연구하는 과정에서 만들어낸 재귀 함수, 엄청나게 빠르게 증가한다.)

(a(n) = 5 가되는 첫 번째 n은 2^(2^(2^65536))이라고 한다., (지구에서 관측할 수 있는 원자의 수는 2^266))

 

 

5. 상호 배타적 집합의 사용 예

 

 

그래프의 연결성 확인하기:

    서로 연결된것 = 하나의 집합 

    (크루스칼의 최소 스패닝 트리 알고리즘)

 

가장 큰 집합 추적하기

     rank처럼 다른 정보를 추가한 뒤 두 집합이 합쳐질때마다 업데이트하여

    합쳐지는 과정에서 집합의 변화를 추적할 수 있다.

 

 

 

 

 

- 알고리즘 문제해결전략 765p