유니온-파인드

유니온-파인드(Union-Find)

독특한 트리의 형태로 상호 배타적 집합(disjoint set) 을 표현할 때 사용된다. 상호 배타적 집합이란, 어떤 두 부분집합 사이에도 교집합이 없고, 모든 부분집합의 합집합인 집합을 의미한다.

두 원소 a, b가 있을 때 이들이 속한 두 집합을 하나로 합치는 과정을 합치기(Union) 연산, 어떤 원소 a가 속한 집합을 반환하는 찾기(find) 연산. 이 두가지가 모여 유니온-파인드(Union-Find) 자료구조라고 부른다.

집합의 표현

1차원 배열에 i 번째 원소가 속하는 집합의 번호를 저장하는 방법이 있다. 찾기에 O(1) 의 시간이 걸리고 합치기에 O(n) 의 시간이 걸린다.

배열을 트리 구조로 생각해 집합의 번호 대신 부모 노드를 저장하는 용도로 사용하면 효율적으로 고칠 수 있다. 루트 노드의 경우 자신의 원소를 저장한다. 두 원소 a, b가 속한 집합를 합치려고 한다면 각각의 루트 노드를 찾아 다른 한쪽의 자손으로 넣으면 되고, 같은 집합에 속해 있는지를 확인하기 위해서는 각 루트의 노드가 같은지를 확인하면 된다.

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

찾기와 합치기 모두 find 함수가 지배하기 때문에 둘 다 트리의 높이에 비례하는 시간을 가진다. 이 때 트리의 형태가 편향되면 합치기, 찾기 모두 시간복잡도가 O(n) 이 되어 집합의 번호를 저장하는 배열보다 더 효율이 나빠질 수 있다.

편향된 트리가 만들어지지 않도록 하기 위해 rank 배열을 추가로 두어 최적화(union-by-rank) 하는 방법이 있다. rank 배열의 역할은 항상 높이가 높은 트리에 낮은 트리를 넣음으로써 전체 트리의 높이가 높아지는 것을 방지한다. rank 배열의 값은 트리의 높이를 의미하므로 같은 높이의 트리를 병합할 경우, 루트가 되는 원소의 rank 값을 증가시켜 주어야 한다.

disjoint set 에서 모든 작업은 루트가 되는 원소를 기준으로 이루어지기 때문에 rank 값은 루트 노드에서만 갱신되어도 문제가 없다. 마찬가지로 find 함수는 항상 특정 원소로부터 루트 원소를 찾아내기 때문에, 같은 경로에 있는 모든 원소의 값을 루트 원소로 바꾸어 주어도 문제가 되지 않고 오히려 중간과정 없이 바로 루트 노드를 찾을 수 있게 되므로 효율적이다. 이런 최적화를 경로 압축(path compression) 최적화라고 부른다.

union-by-rank 최적화 만으로도 복잡도는 O(logn) 으로 줄게되고 path compression 최적화로 더욱 빨라지게 된다.

struct disjointSet{
    vector<int> parent, rank;
    disjointSet(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 parent[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]++;
    }
};