BOJ 1922 네트워크 연결 (MST, UnionFind)

문제

모든 컴퓨터(노드)를 연결하되, 연결 비용의 총합을 최소일때 연결비용 구하기.

제약 조건: $N \le 1,000$, $M \le 100,000$.

복잡도 분석

• 간선 저장 및 정렬 - $M$개의 간선을 가중치 순으로 정렬 - $O(M \log M)$
• Union-Find 초기화 - $N$개의 노드에 대해 부모 배열 초기화 - $O(N)$
• 사이클 판별 및 합치기 - $M$번의 find 및 unite 연산 - $O(M \cdot \alpha(N))$

최종 복잡도 - $O(M \log M)$

접근법

최소 신장 트리(Minimum Spanning Tree, MST) 문제임

처음에 간선 리스트로 받고, 가중치로 정렬한다. 이후 Kruskal 알고리즘으로 그리디 접근 방식으로 비용이 낮은것부터 연결. n개 vertex의 경우 n-1개 연결했으면 끝이다

연결은 union find 로 한다. find에서 경로압축하고, union에서는 랭크 따지면서 합치기(이 문제는 안해도 되는것 같기는 함)

풀이

#include <bits/stdc++.h>
using namespace std;

int n,m;
struct Edge{
    int c,u,v;
    bool operator<(const Edge &other) const{
        return c<other.c;
    }
};
vector<Edge> v;
vector<int> parent;
vector<int> rnk;

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

bool _union(int a, int b){
    a = find(a);
    b = find(b);
    if (a==b) return false;

    if (rnk[a]<rnk[b]) parent[a] = b;
    else if (rnk[a]>rnk[b]) parent[b] = a;
    else {
        parent[b] = a;
        rnk[a]++;
    }
    return true;
}

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

    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v1,c; cin>>u>>v1>>c;
        v.push_back({c,u,v1});
    }

    sort(v.begin(),v.end());
    for(int i=0;i<n+1;i++){ // 0번 버림
        parent.push_back(i);
    }
    rnk.resize(n+1,0);

    int connected = 0;
    int cost = 0;
    for(int i=0;i<size(v);i++){
        Edge X = v[i];
        if (_union(X.u,X.v)){
            cost += X.c;
            connected ++;
        }
        if (connected==n-1) break;
    }
    cout << cost; 
    return 0;
}

예전에는 파이썬으로만 풀었었나? 그리고 rank라고 이름지으면 안되는듯. 배열의 차원 구하는거라고 한다.

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

bool _union(int a, int b){
    a = find(a);
    b = find(b);
    if (a==b) return false;

    if (rnk[a]<rnk[b]) parent[a] = b;
    else if (rnk[a]>rnk[b]) parent[b] = a;
    else {
        parent[b] = a;
        rnk[a]++;
    }
    return true;
}

cpp로 처음해서 익숙하지 않았음. 이전에는 is_union함수를 따로 만들었는데. 이렇게 하면 필요가 없네