백준: Class 5 - 1647: 크루스칼 알고리즘(Union find)

</br> 크루스칼 알고리즘을 저번 포스트, 1197: 최소 스패닝 트리(https://cyj893.github.io/algorithm/Algorithm12_2/)를 풀 때 사용하긴 했다.
그런데 그대로 1647번을 풀었더니 시간 초과가 나더라!!

그래서 찾아 보니 Union find를 사용하면 시간을 효과적으로 줄여 준다더라.
부모를 찾는 find 작업과 부모를 합치는 merge 작업으로 이루어져 있다.

</br>

1197: 기존 코드(Union find 사용 X)

priority_queue<T, vector<T>, greater<T>> pq;
    for(int i = 0; i < e; i++){
        int a, b, c;
        cin >> a >> b >> c;
        pq.push(mt(c, a, b));
        parent[a] = a;
        parent[b] = b;
    }
    int ans = 0;
    while( pq.size() ){
        T t = pq.top();
        pq.pop();
        int ta = get<1>(t);
        int tb = get<2>(t);
        if( parent[ta] == parent[tb] ) continue;
        int p = min(parent[ta], parent[tb]);
        int pp = max(parent[ta], parent[tb]);
        for(int i = 1; i <= v; i++){
            if( parent[i] == pp ) parent[i] = p;
        }
        ans += get<0>(t);
    }
    cout << ans << endl;

기존 코드에서는 부모를 찾고 바꾸는 일이 배열을 통해 이루어지므로, O(N) 시간으로 걸린다.
</br>

1197: 바꾼 코드(Union find 사용)

#include <bits/stdc++.h>

using namespace std;

struct UnionFind{
	vector<int> parent, ran;
    UnionFind(int n) : parent(n+1), ran(n+1, 1){
    	for(int i = 1; i <= n; i++){
            parent[i] = i;
    	}
    }
    int f(int u){
    	if( u == parent[u] ) return u;
    	parent[u] = f(parent[u]);
        return parent[u];
    }
    bool merg(int u, int v){
    	u = f(u); v = f(v);
        if( u == v ) return false;
        if( ran[u] > ran[v] ) swap(u, v);
        parent[u] = v;
        ran[v] += ran[u];
        ran[u] = 0;
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    priority_queue< tuple<int, int, int>, vector<tuple<int, int, int>>, greater<> > pq;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        pq.push(make_tuple(c, a, b));
    }

    UnionFind uf = UnionFind(n);
    int ans = 0;
    //int last;
    while( pq.size() ){
        int c = get<0>(pq.top());
        int a = get<1>(pq.top());
        int b = get<2>(pq.top());
        pq.pop();

        if( uf.merg(a, b) ) ans += c;
    }

    cout << ans << endl;

}

Union find를 사용하면, 트리 형식이 되기 때문에 작업을 O(logN)으로 확연히 줄일 수 있다.

</br>

Union find

struct UnionFind{
	vector<int> parent, ran;
    UnionFind(int n) : parent(n+1), ran(n+1, 1){
    	for(int i = 1; i <= n; i++){
            parent[i] = i;
    	}
    }
    int f(int u);
    bool merg(int u, int v);
};

우선 부모 배열과 랭크 배열을 만든다.
parent(n+1), ran(n+1, 1) 이 부분 유의하세요
대부분 문제는 1~n까지 인덱스니까 그대로 사용하려면 이렇게 선언해야 함
현재 부모들은 다 자기 자신이고, 현재 랭크도 자기밖에 없으므로 1이다.

    int f(int u){
    	if( u == parent[u] ) return u;
    	parent[u] = f(parent[u]);
      return parent[u];
    }

find 작업이다.
만약 내가 내 부모면 바로 나를 리턴한다.
그게 아니면 재귀로 내 부모를 업데이트하며 찾아내고 리턴한다.

    bool merg(int u, int v){
    	u = f(u); v = f(v);
        if( u == v ) return false;
        if( ran[u] > ran[v] ) swap(u, v);
        parent[u] = v;
        ran[v] += ran[u];
        ran[u] = 0;
        return true;
    }

merge 작업이다.
이건 최적화된 건데, 트리의 경우 치우치면 성능이 구려서 O(N)이 되므로 균형좋게 만들기 위해 랭크가 사용되는 거다.
랭크가 작은쪽의 부모를 큰쪽으로 하고, 큰쪽의 랭크에 작은쪽의 랭크를 더한다.
작은쪽은 이제 아무것도 없으므로 0이 된다.
</br>

1647: 도시 분할 계획

https://www.acmicpc.net/problem/1647

    priority_queue< tuple<int, int, int>, vector<tuple<int, int, int>>, greater<> > pq;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        pq.push(make_tuple(c, a, b));
    }

    UnionFind uf = UnionFind(n);
    int ans = 0;
    int last;
    while( pq.size() ){
        int c = get<0>(pq.top());
        int a = get<1>(pq.top());
        int b = get<2>(pq.top());
        pq.pop();

        if( uf.merg(a, b) ){
            ans += c;
            last = c;
        }
    }

    cout << ans-last << endl;

1647번의 경우, 최소 스패닝 트리를 구한 뒤 마지막에 추가한 간선만 빼 버리면 두 부분으로 나눌 수 있다.
</br>

---

약간 헛돌아서 좀 뻘짓했지만 이제 익혔으니 됐다
</br>