티스토리 뷰

반응형

Table of Contents


개요

초기화

간단한 방법

최적화 단계 1

최적화 단계 2 - 유니온 파인드 트리

유니온 파인드 트리 - 코드

문제




1. 개요


 유니온 파인드는 집합을 관리하는 자료구조로서, disjoint set 이라고 부르기도 합니다. 이 자료구조를 활용하면 아래의 두 가지 연산을 사용할 수 있습니다.


연산 1) 요소 A와 요소 B가 같은 집합에 속하는 지 확인.

연산 2) 요소 A가 속한 집합과 요소 B가 속한 집합을 병합.



 유니온 파인드 연산의 이해를 위해  일단, 위와 같이 4개의 요소가 있다고 해보겠습니다. 초기 상태는 아직 병합을 한 번도 안 한 상태이기 때문에 각자 다른 집합에 속합니다.



 이 상태에서 1번 연산, 예를 들어 요소 1과 요소 2가 같은 집합 인지에 대한 질의가 들어오면 이 자료구조는 NO를 반환합니다. 2번 연산의 예로, 요소 1이 속한 집합과 요소 2가 속한 집합을 병합하게 되면 아래와 같이 상태가 변화합니다.



 이 상황에서 다시 1번 연산, 요소 1과 요소 2가 같은 집합 인지에 대한 질의가 들어오면 이번엔 YES를 반환하게 되지요. 그 다음, 2번 연산으로 요소 1이 속한 집합과 요소 4가 속한 집합을 병합하면 아래와 같이 상태가 변화합니다.



 이런 식의 두 연산을 효율적으로 하기 위한 자료구조가 유니온 파인드, disjoint set 입니다. 따라서 아래와 같이 기본 구조를 잡을 수 있습니다.


1
2
3
4
5
6
7
//code by RiKang, weeklyps.com
 
struct union_find{
    void init(int uf_n){...} // 요소 uf_n개로 초기화
    bool same_set(int v1, int v2){...} // 요소 v1, v2은 같은 집합에 속하는가?
    void merge(int v1,int v2){...} // 요소 v1, v2가 속한 두 집합을 병합
}uf;
cs




2. 초기화


 초기 상태는 각각의 요소가 따로 따로 집합에 속하는 상태입니다. 이 상태를 만들어 주는 간단한 방법으로, 'i 번째 요소는 i 번째 집합에 속한다.' 라고 지정하는 방법이 있습니다. 아래와 같은 코드로 간단하게 가능합니다.


1
2
3
4
5
6
7
8
9
10
11
//code by RiKang, weeklyps.com
struct union_find{
    vector<int> group;     // group[i] = i번째 요소가 속한 집합의 번호
    void init(int uf_n){ // 요소 uf_n개로 초기화
        group.clear();
        for(int i=0; i<uf_n; i++)
            group.push_back(i);
    }
    bool same_set(int v1, int v2){...} // 요소 v1, v2은 같은 집합에 속하는가?
    void merge(int v1,int v2){...} // 요소 v1, v2가 속한 두 집합을 병합
}uf;
cs




3. 간단한 방법


 이 파트에서는 유니온 파인드를 구현하는 간단한 방법에 대해 소개합니다. 단, same_set()함수의 시간복잡도는 O(1), merge()함수의 시간복잡도는 O(N)으로 효율은 좋지 않습니다.


 우선 초기화 파트에서 설정한 group 배열을 가지고 있다면, same_set 연산은 굉장히 간단해 집니다. 요소 A와 요소 B가 같은 집합에 속하는 지에 대한 판별은 group[A]==group[B] 로 가능하기 때문이지요.


 병합의 경우엔, 요소 B가 속한 집합의 요소들을 전부 요소 A가 속한 집합으로 옮기면 됩니다. 따라서 아래와 같이 코딩할 수 있습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//code by RiKang, weeklyps.com
struct union_find{
    vector<int> group;     // group[i] = i번째 요소가 속한 집합의 번호
    void init(int uf_n){ // 요소 uf_n개로 초기화
        group.clear();
        for(int i=0; i<uf_n; i++)
            group.push_back(i);
    }
    bool same_set(int v1, int v2){ // 요소 v1, v2은 같은 집합에 속하는가?
        return group[v1]==group[v2];
    }
    void merge(int v1,int v2){ // 요소 v1, v2가 속한 두 집합을 병합
        int remove_group = group[v2];
        for(int i=0; i<group.size(); i++)
            if(group[i] == remove_group)
                group[i] = group[v1];
    }
}uf;
cs


 간단하지만, merge 의 if 문에 group[i] == group[v2] 로 하면 안되는 점은 주의해야 합니다. 그럴 경우, 반복문 중간에 group[v2]가  group[v1] 으로 바뀌기 때문에 i > v2 인 요소들은 제대로 병합이 되지 않습니다.


 이 간단한 방법을 활용하면 same_set()함수의 시간복잡도는 O(1), merge()함수의 시간복잡도는 O(N)이며, 또한 모든 요소가 하나의 집합이 될 때까지의 총 시간 복잡도는 O(N^2) 입니다. 이는 굉장히 비효울적인 시간 복잡도이기 때문에 잘 쓰이지 않습니다.


 아래에서는 이 시간 복잡도를 개선할 수 있는 방법을 2단계로 나누어 소개합니다. 2가지 단계 중에서 많은 사람들이 유니온 파인드를 사용할 때 쓰는 건 단계 1보다 대부분의 상황에서 더 빠른 단계 2입니다. 유니온 파인드 자료구조에 대한 정보만 알고 싶다면 단계 1을 보지 않고 단계 2로 바로 넘어가셔도 상관없습니다. 하지만 단계 1에서 사용하는 최적화 스킬은 유니온 파인드 이외에 여러가지 다른 상황에서도 유용하게 쓰이니, 같이 봐두는 것이 좋습니다.




4. 최적화 단계 1


 단계 1의 아이디어는 '각 집합에 어떤 요소들이 있는 지를 저장하면, merge 에서 모든 요소들을 순회할 필요가 없다.'는 것입니다.


members[i] = i 집합에 속한 요소들의 번호들을 저장한 동적 배열

members[i][j] = i 집합에 속한 요소 중 j 번째 요소


 이런 식으로 저장해놓으면, merge()함수에서 group[v2]와 같은 그룹인 요소들만 쏙쏙 고를 수 있게 됩니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//code by RiKang, weeklyps.com
struct union_find{
    vector<int> group;     // group[i] = i번째 요소가 속한 집합의 번호
    vector<vector<int> > members; // members[i] = i 집합에 속한 요소들의 번호
    void init(int uf_n){ // 요소 uf_n개로 초기화
        group.clear();
        members.clear();
        members.resize(uf_n);
        for(int i=0; i<uf_n; i++){
            group.push_back(i);
            members[i].push_back(i);
        }
    }
    bool same_set(int v1, int v2){ // 요소 v1, v2은 같은 집합에 속하는가?
        return group[v1]==group[v2];
    }
    void merge(int v1,int v2){ // 요소 v1, v2가 속한 두 집합을 병합
        int remove_group = group[v2];
        for(auto now: members[remove_group]){
            group[now] = group[v1];
            members[v1].push_back(now);
        }
    }
}uf;
cs


 위의 코드를 통해 병합할 경우, 속한 집합이 group[v2] 인 요소들만 골라서 순회함을 확인하실 수 있습니다. 하지만 merge 의 시간복잡도가 O(N) 인 것은 변하지 않으며, 모든 요소가 하나의 집합이 될 때까지 총 시간 복잡도는 여전히 O(N^2) 입니다.


 이제 아래와 같이 merge 를 한 번 더 최적화 해주면, 모든 요소가 하나의 집합이 될 때까지 총 시간 복잡도가 O(N log N)으로 확 줄어들게 됩니다.


1
2
3
4
5
6
7
8
9
10
//code by RiKang, weeklyps.com
    void merge(int v1,int v2){ // 요소 v1, v2가 속한 두 집합을 병합
        if(members[group[v1]].size() < members[group[v2]].size())
            swap(v1,v2); // 최적화 추가, v1과 v2를 서로 바꾼다.
        int remove_group = group[v2];
        for(auto now: members[remove_group]){
            group[now] = group[v1];
            members[v1].push_back(now);
        }
    }
cs


 추가한 것은 집합 group[v1] 의 요소 개수가, 집합 group[v2]의 요소 개수보다 작을 때, v1 과 v2를 서로 바꾼 부분입니다. 반복문에서 '집합 group[v2]의 요소 개수' 만큼 순회하므로, 이렇게 하면 조금 더 빨라지는 건 당연한 일입니다. 하지만 merge 의 최악 시간 복잡도는 여전히 O(N) 이며, 이 점 때문에 모든 요소가 하나의 집합이 될 때까지 총 시간 복잡도도 O(N^2) 이라고 착각할 수 있습니다.


 이 착각에서 놓친 중요한 부분은 집합 group[v2]의 크기가 반복문 전과 후, 최소 2배 차이가 난다는 점입니다. 추가한 최적화로 인해


병합 이후 크기 = (병합 전)집합 group[v1]의 크기 + 집합 group[v2]의 크기 >= (병합 전)집합 group[v2]의 크기 * 2


 라는 식이 성립하기 때문이지요. 따라서 시점을 바꾸어, 각 요소 i 마다 group[i] 가 최대 몇 번 변할 수 있는 지를 생각해 보면 총 시간 복잡도가 O(N log N) 라는 걸 알 수 있습니다.


1. 요소 i 가 초기화 되었을 때, 집합 group [ i ] 의 크기는 1이다. ( 집합에 i 밖에 없다.)

2. group[i] 가 1번 변경 된 이후, 집합 group [ i ] 의 크기는 2 이상이다.

3. group[i] 가 2번 변경 된 이후, 집합 group [ i ] 의 크기는 4 이상이다.

4. group[i] 가 3번 변경 된 이후, 집합 group [ i ] 의 크기는 8 이상이다.

...

??. group[i] 가 대략 log N 번 변경 된 이후, 집합 group [ i ] 의 크기는 N 이상이다.


 이를 통해 각 요소마다 group[i] 의 변경은 O(log N) 번 일어남을 알 수 있습니다. 요소는 N 개 이므로, 병합을 모두 할 때 까지 시간 복잡도는 O(N log N)이 됩니다.


 이처럼, 큰 집합과 작은 집합을 병합할 때 N, 큰 집합의 요소 개수, 작은 집합의 요소 개수 는 모두 다른 존재일 수 있습니다. 항상 이들을 묶어서 O(N)이라고 생각하고 넘어간다면, 프로그램 전체를 보았을 때 O(N^2) -> O(N log N) 이 되는 큰 변화를 놓칠 수 있습니다. 유니온 파인드가 아니라 다른 상황에서도, 이처럼 두 집합을 관한 연산을 할 때 작은 집합의 요소 개수만큼 연산하여 전체 시간 복잡도를 줄이는 경우가 종종 있습니다.




5. 최적화 단계 2 - 유니온 파인드 트리


 단계 1에서 집합을 벡터로 관리하던 members와 group을 없애고, 각 집합을 배열이 아닌 트리의 형태로 관리하면 더 빠른 자료구조를 만들 수 있습니다. 이 방법의 경우, 각 요소들마다 group[i] 를 저장하는 것이 아니라 parent[i], 즉, 트리에서의 부모를 저장합니다. 개요에 있는 상황을 트리로 표현하면 아래와 같습니다.



 이 방법에서는 집합의 번호를 루트 요소의 번호로 대신합니다. 따라서 집합의 번호(group[i]) 를 찾고 싶을 땐, 루트 노드를 찾아 올라가면 됩니다. i가 루트인 경우엔, parent[i] = i 를 저장하여 루트임을 암시해 놓는 것이 구현하기 편합니다. (이렇게 하면 초기화 과정은 윗 단계에서 group 의 초기화 과정과 동일합니다.)


 위 그림의 상황에서 parent를 정리하면 아래와 같습니다.


parent []= {0, 1, 1, 3, 4}   // (1->1) (2->1) (3->3) (4->1)


 이런 parent 가 있으면 아래와 같이 집합의 번호를 찾을 수 있습니다.


1
2
3
4
5
//code by RiKang, weeklyps.com
int get_root(int now){
    if(parent[now]==now) return now;
    return get_root(parent[now]);
}
cs


 if 에 걸리면 now 노드가 root라는 것이므로 now를 반환하며, 그게 아니라면 parent 를 통해 위로 올라갑니다. 이 부분을 좀 더 최적화 하면 아래와 같습니다.


1
2
3
4
5
//code by RiKang, weeklyps.com
int get_root(int now){
    if(parent[now]==now) return now;
    return parent[now] = get_root(parent[now]);
}
cs


 한 번 호출 되었을 때, 경로에 있는 모든 노드의 parent를  root 로 연결 시키는 작업을 추가하였습니다. 이렇게 하면 get_root() 가 다시 호출 되었을 시, parent[] 가 루트 노드를 가리키기 때문에 재귀호출이 빨리 끝나게 됩니다.


 이제 이 get_root() 를 통해 최적화 단계 1 까지 사용하였던 group[] 을 대신할 수 있습니다.


 다음은 merge 부분입니다. 병합할 때는 한 집합의 root 의 parent 를 다른 집합의 root로 설정하면 끝입니다.


1
2
3
4
5
//code by RiKang, weeklyps.com
void merge(int v1,int v2){
    v1=get_root(v1), v2=get_root(v2);
    parent[v2] = v1;
}
cs


 위의 그림에서 merge(1,3) 이 호출되면 parent[3] = 1이 되므로 아래와 같이 자료구조가 변형됩니다.



 만일 3 밑에 다른 요소가 있었더라도, 그 요소에서 root를 찾으면 1이 됨은 쉽게 알 수 있습니다. parent[3] = 1 연산 한 번으로, 루트 노드가 3이었던 모든 노드들의 루트가 1로 변화된 것이지요.


 위에서 했던 get_root() 의 최적화 때문에, 이 것도 꽤 빠르지만 단계 1에서와 비슷한 아이디어를 통해 더 최적화 할 수 있습니다. 항상 작은 집합을 큰 집합에 포함되도록 만들면, 이후에 get_root() 연산이 들어올 때 parent 를 조금 덜 찾을 수 있지요.


 get_root() 의 최적화를 위해 아래의 코드에서는 트리의 높이가 낮은 트리를 작은 집합이라고 정의하였습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//code by RiKang, weeklyps.com
struct union_find_tree{
    vector<int> parent;
    vector<int> height;
 
    void init(int uf_n){
        parent.clear();
        height.clear();
        for(int i=0; i<uf_n; i++){
            parent.push_back(i);
            height.push_back(0);
        }
    }
 
    int get_root(int now){
        if(parent[now]==now) return now;
        return parent[now] = get_root(parent[now]);
    }
 
    void merge(int v1,int v2){
        v1=get_root(v1), v2=get_root(v2);
        if(v1==v2) return;
        if(height[v1] < height[v2]) swap(v1,v2);
        parent[v2]=v1;
        if(height[v1]==height[v2]) height[v1]++;
    }
}uf;
cs


 이 최적화 과정들을 끝낸 유니온 파인드를 사용하면, 각 연산의 평균 시간 복잡도는 에커만 함수의 역함수로 알려져 있습니다. 이 함수가 얼마나 큰지 감각적으로 알기 힘들다면, 'O(1) 보다 느리고 O(logN) 보다 빠르다.' 정도로 기억하면 됩니다. 즉, 모든 요소가 하나의 집합에 속할 때 까지의 총 시간복잡도는 O(N) 보다 느리고 O(N logN)보다 빠릅니다.




6. 유니온 파인드 트리 - 코드


 유니온 파인드를 응용하는 상황에 대비해, 각 집합의 요소의 개수도 같이 저장한 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#include<vector>
 
using namespace::std;
 
const int N=1000000;
 
struct union_find_tree{
    vector<int> parent;
    vector<int> height;
    vector<int> group_size;
 
    void init(int uf_n){
        parent.clear(), height.clear();
        group_size.clear();
        for(int i=0; i<uf_n; i++){
            parent.push_back(i);
            height.push_back(0);
            group_size.push_back(1);
        }
    }
 
    int get_root(int now){
        if(parent[now]==now) return now;
        return parent[now] = get_root(parent[now]);
    }
    
    bool same_set(int v1, int v2){
        return get_root(v1)==get_root(v2);
    }
 
    void merge(int v1,int v2){
        v1=get_root(v1), v2=get_root(v2);
        if(v1==v2) return;
        if(height[v1] < height[v2]) swap(v1,v2);
        parent[v2]=v1;
        group_size[v1]+=group_size[v2];
        if(height[v1]==height[v2])
            height[v1]++;
    }
}uf;
 
int main(){
    return 0;
}
cs




7. 문제


(0) [BOJ 1717] 집합의 표현



(1) [BOJ 1976] 여행 가자



(2) [BOJ 9938] 방 청소


(3) [BOJ 10775] 공항


(4) [CF 411 D] Expected diameter of a tree



※ 본문의 코드들은 C++ 17 환경에서 작성되었습니다.

※ 문의 : rikang93@gmail.com


반응형

'그래프 ( Graph )' 카테고리의 다른 글

프림 알고리즘 ( Prim's algorithm )  (1) 2017.11.28
트리의 지름  (0) 2017.11.25
크루스칼 알고리즘 ( Kruskal's algorithm )  (0) 2017.11.23