[BOJ] 1922 네트워크 연결

문제: https://www.acmicpc.net/problem/1922

 MST(최소 비용 신장 트리, Minimum Spanning Tree)를 찾는 문제로 정말로 naive하게 MST를 찾는 알고리즘을 구현해주면 된다. 나는 이 문제를 풀기 위해서 크루스칼 알고리즘을 사용했다. 지금 생각해 보니 좀 많이 이상하지만 정보올림피아드를 이제까지 준비하면서 단 한번도 MST를 사용하는 문제를 풀거나 코딩해 본적이 없었다. Union-Find (코드에서 DisJointSet)을 좀 쉽게 구현할 수 있게 되니까 비로소 알고리즘을 이해할 수 있었다. 난이도는 1.5/5 정도인 것 같고 코드는 아래와 같다.

#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
typedef struct DisJointSet
{
    vector<int> parent;
    vector<int> ra;
    DisJointSet(int s)
    {
        parent.assign(s+1,0);
        ra.assign(s+1,1);
        for(int i=1;i<=s;i++)
            parent[i]=i;
    }
    int fi(int a)
    {
        if(a==parent[a]) return a;
        else return parent[a]=fi(parent[a]);
    }
    void un(int a, int b)
    {
        a=fi(a); b=fi(b);
        if(a==b) return;
        if(ra[a]<ra[b]) swap(a,b);
        parent[b]=a;
        if(ra[a]==ra[b]) ra[a]++;
    }
}DJS;
 
int main()
{
    vector<pair<int, pair<int,int> > > V;
    int n,m,sum=0;
    scanf("%d %d",&n,&m);
    DJS S(n);
    for(int i=0;i<m;i++)
    {
        int t1,t2,t3;
        scanf("%d %d %d",&t1,&t2,&t3);
        V.push_back(make_pair(t3,make_pair(t1,t2)));
    }
    sort(V.begin(),V.end());
    for(int i=0;i<V.size();i++)
    {
        int a=V[i].second.first;
        int b=V[i].second.second;
        int cost=V[i].first;
        if(S.fi(a)==S.fi(b)) continue;
        S.un(a,b);
        sum+=cost;
    }
    printf("%d",sum);
    return 0;
}
 

간선들을 가중치 순서대로 정렬하고 cycle이 생기지 않다는 전제 하에 (Union Find Tree로 확인) greedy하게 간선을 MST에 추가해 주면 되는 방식이다. 구현 자체는 생각보다 쉽다.