유니온 파인드(Union-Find), 서로소 집합(Disjoint Set)

문제를 풀다보니까, 유니온-파인드 개념이 어려운게 아니라, 어려운 그리디 문제가 많은것 같다(형식만 유니온-파인드인)

 

일단 개념은 여기, 여기, 여기, 여기, 여기가 배우기 좋다.

교집합이 없는 서로소 집합(Disjoint Set)이라고도 불린다.

union연산과 find연산 단 2개만을 지원하는 자료구조로 disjoint한 집함들을 표현하는 자료구조.

따라서 도로 분할하는건 굉장히 힘들지만 보통 합치는 방향만 필요할때 유용.

이게 표현하려는 집합은 어떤 두 집합 사이에도 교집합 원소가 하나도 없고, 모든 집합의 합집합은 전체집합이라는 뜻.

따라서 파티션과 같다. 기본적으로 set마다 하나의 트리를 이루므로 forest(숲)의 형태를 띈다. (숲 = 트리의 집합)

 

 

근데 굳이 이걸 왜쓰는지가 중요한데,

트리구조 여러개를 다루면서 동적으로 변하는 구조에 대해서는 기존 STL만 가지고 핸들링하기 한계가 있는것 같음

근데 다른 자료구조에 비해 실무적인 연관성이 상당히 떨어져 보이기는 한다.

문제를 위해 꼬으고 꼬은 것처럼 보인달까? 

 

아무튼 disjoint set 마다 트리를 하나씩 가지게 하자는 개념인데..

 

초기화

최초 한 번만 수행되며, N개의 서로 독립적인 트리를 만들어 주는 단계 (모든 노드가 root 노드)

 

Find

Finx(x)는 노드 x의 부모중 루트를 반환하는 연산을 한다. 

disjoint set에서 임의의 두 노드들이 같은 집합에 속해있는지 확인하는 방법은 Find()로 나오는 값이 같은지 보는것.

Find연산의 시간복잡도는 트리의 높이 h에 비례 하므로 경로 압축과정을 통해 넓고 얕게 트리를 유지하는 코드가 들어가게 된다.

 

 

 --> 

이렇게..

 

Union

초기화랑 find만 있으면 당연히 의미가 없고, 같은 set에 포함된 노드들을 합치는 연산이 필요하다. 그게 union이고, 

두개의 트리를 합치는 작업이 들어가는데, 합쳐진 트리의 높이를 낮게 유지하기 위해 작은 트리의 부모를 큰 트리의 root로 하는 작업을 해주게 된다. 이걸 랭크압축이라고 하며, 여기를 참조하자.

 

시간복잡도

union연산의 복잡도도 find연산이 지배함.

find연산은 노드개수 N개, 연산수 M개일때 O(Mlog*N)인데 log*N이 워낙 작은 값이라 O(M)으로 봐도 좋다고 한다.

즉 거의 상수시간에 find, union연산이 되는것

 

 

재활용코드

아래는 내가 처음 짜본 union-find 코드이다. 이 문제의 답안이기도 하다.

경로압축과 랭크압축중 경로압축만 간단하게 되어 있다.(경로압축 안할경우 TLE발생)

코드 작성 자체는 매우 심플하고 구현하기 쉬웠다.

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
int n, m, op, x, y;
int find(int x, vector<int>&parent){
    int ox = x;
    while(parent[x]!=x) x=parent[x];
    parent[ox]=x;  // 여기, 경로압축
    return x;
}
 
void uni(int x, int y, vector<int>&parent){
    int xp = find(x,parent), yp = find(y, parent);
    //임의로 y를 x에 붙여보자.
    parent[yp]=xp;
}
 
int32_t main()
{
    scanf("%d%d", &n,&m);
    vector<int> parent(n+1);REP1(i,n)parent[i]=i;
    REP(i,m){
        scanf("%d%d%d", &op,&x,&y);
        if(op==0){  //union
            uni(x,y,parent);
        }else{  //find
            printf("%s\n", find(x, parent)==find(y, parent)?"YES":"NO");
        }
    }
    return 0;
}

 

실제 재활용하기에는 아래코드가 더 좋은것 같다(캡슐화되어 있고, 좀더 효율적인 경로압축, 랭크압축 되어 있음)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
const int INF = (int)1e9;
 
struct union_find{
    vector<int> p,r;
    union_find(int n){
        p.resize(n+1), r.resize(n+1);
        for (int i=0; i<=n; i++) {
            p[i] = i;
        }
    }
    int find(int x){
        if(p[x] == x) return x;
        else return p[x] = find(p[x]);
    }
 
    void uni(int a, int b){
        a = find(a);
        b = find(b);
        if(r[a] < r[b]) p[b] = a;
        else p[a] = b;
        if(r[a] == r[b]) r[a]++;
    }
};
 
int n, m, op, x, y;
int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
#endif
 
    scanf("%d%d", &n,&m);
    union_find uf(n);
    REP(i,m){
        scanf("%d%d%d", &op,&x,&y);
        if(op==0) uf.uni(x,y);
        else printf("%s\n", uf.find(x)==uf.find(y)?"YES":"NO");
    }
    return 0;
}
 

 

아래는 uni()함수에서 합쳐진 집합의 크기를 리턴하도록 개선한 버전(내꺼 초기버전 베이스로 만들었다)

이 문제의 답안이기도 하다. 이버전이 랭크압축한거 보다 오히려 왼쪽으로 정렬되는 효과가 있어서 일부문제에서는 더 좋았다.

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
 
struct union_find {
    vector<int> parent, cnt;
    union_find(int n) {
        parent.resize(n + 1), cnt.resize(n + 1);
        REP1(i, n)parent[i] = i, cnt[i] = 1;
    }
    int find(int x) {
        if (parent[x] == x) return x;
        else return parent[x] = find(parent[x]);
    }
 
    int uni(int x, int y) {
        int xp = find(x), yp = find(y);
        //임의로 y를 x에 붙여보자.
        if (xp != yp) {
            cnt[xp] += cnt[yp];
            parent[yp] = xp;
        }
        return cnt[xp];  // 합친 집합의 개수를 리턴
    }
};
 
int T, F, ix;
string s1, s2;
int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> T; while (T--) {
        cin >> F;
        map<string, int> m; ix = 0;
        union_find uf(2 * F);
        while (F--) {
            cin >> s1 >> s2;
            if (m.count(s1) == 0)m[s1] = ++ix;
            if (m.count(s2) == 0)m[s2] = ++ix;
            cout << uf.uni(m[s1], m[s2]) << '\n';
        }
    }
    return 0;
}