[자료구조/C, C++] Disjointed Set (2)

정형주·2020년 9월 24일

자료구조

목록 보기

4/5

앞장에서 가장 기초적인 disjointed set 구현 방법을 알아보았습니다.
하지만 서로 다른 두 원소의 집합을 합치는 union 연산,
두 원소가 같은 집합에 있는지 확인하는 find 연산의 시간 복잡도는 O(n)으로 n이 커진다면 disjointed set을 구하는데 많은 시간이 필요합니다.

백준 사이트의 문제 1717번 : 집합의 표현
문제는 앞서 다룬 disjointed set 알고리즘만으로는 정해진 시간 내에 풀 수 없습니다.

다음과 같이 find와 union을 최적화하여 문제를 해결할 수 있습니다.

find를 최적화 하는 방법

경로 압축을 사용하여 find(getParent)를 최적화 할 수 있습니다.

트리 구조가 연결리스트 형태인 경우

경로 압축(Path Compression)

경로 압축 구현코드

int getParent(int a){
    if(a == parent[a]) return a;
    return parent[a] = getParent(parent[a]);
}

시간복잡도 : O(logn)

union을 최적화 하는 방법

각 원소가 속한 집합의 높이를 저장하는 배열 rank를 이용하여 최적화합니다. 한 트리의 rank 값에 따라 집합에 포함되거나 포함하는 기준을 정합니다.
높이가 낮은 트리를 높이가 높은 트리 안에 넣으면 집합의 최대 높이를 유지할 수 있습니다.
두 집합의 높이가 같을 경우는 한 집합이 다른 집합의 자식이 되고 rank의 값을 1 높힙니다.

union-by-rank 구현 코드

void Union(int a, int b){
    int parentA = getParent(a);
    int parentB = getParent(b);
    
    if(parentA == parentB) return;
    //union 기준 : rank가 높은 집합 기준으로 병합
    if(rank[parentA] < rank[parentB]){
        parent[parentA] = parentB;
    }else{
        parent[parentB] = parentA;
    }
    
    if(rank[parentA] == rank[parentB]){
        rank[parentA]++;
    }
}

전체 소스코드

#include <iostream>
using namespace std;
int n, m, parent[1000001], treerank[1000001];

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

void union_parent(int x, int y){
    int parentx = find(x);
    int parenty = find(y);
    if(parentx==parenty) return;
    
    if(treerank[parentx] < treerank[parenty]){
        parent[parentx] = parenty;
    }else{
        parent[parenty] = parentx;
    }
    if(treerank[parentx] == treerank[parenty]){
        treerank[x]++;
    }
    return;
}

int main(){
    ios :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m;
    for(int i = 0 ; i<=n ; i++){
        parent[i] = i;
        treerank[i] = 0;
    }
    for(int i = 0 ; i<m ; i++){
        int op, a, b;
        cin >> op >> a >> b;
        if(op==0){
            union_parent(a, b);
        }else{
            if(find(a)==find(b)) cout << "YES" <<'\n';
            else cout << "NO" <<'\n';
        }
    }
    return 0;
}