BOJ 1197 최소 스패닝 트리 (MST)

 

문제 링크 : https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

최소 신장 트리를 구하는 데에는 대표적인 두 알고리즘인 Prim 알고리즘과 Kruskal 알고리즘이 있다.

두 가지 모두 구현하고 몇 가지 첨언한다.

 

1. Kruskal Algorithm

간선의 가중치를 오름차순으로 정렬하여 하나씩 조사한다.

기존에 선택된 간선들과 cycle 을 형성하지 않으면 선택한다.

cycle 을 확인하는 방법으로 find-union 을 사용해서 간선 양끝이 같은 집합에 속하는지를 본다.

 

간선을 정렬해야하므로 간선의 개수를 E 라 하면 수행 시간은 \(O(E \log E) \) 을 따르게 된다.

간선의 개수가 많다면 \(O(E \log V)\) 로 동작하는 Prim 알고리즘에 비해 구현은 쉽고 속도는 느리다.

(하지만 본 문제에서는 간선의 개수가 그리 많지 않아서 의미 있는 속도 차이는 느낄 수 없었다.)

 

#include<bits/stdc++.h>

using namespace std;

int n,m,ans;

struct edge {
    int cst, u,v;
    bool operator<(edge &rhs){
        return cst < rhs.cst;
    }
};
vector<edge> Edges;

int prv[10001], sz[10001];

int belong(int u){
    return u==prv[u]?u:prv[u]=belong(prv[u]);
}

void link(edge &e){
    int u=belong(prv[e.u]), v=belong(prv[e.v]);
    if(u==v) return;
    
    ans+=e.cst;
    if(sz[u]<sz[v]) swap(u,v);
    prv[v]=u;
    sz[u]+=sz[v];
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) prv[i]=i, sz[i]=1;
    
    for(int i=0;i<m;i++){
        int u,v,c; scanf("%d%d%d",&u,&v,&c);
        Edges.push_back({c,u,v});
    }
    
    sort(begin(Edges), end(Edges));
    for(auto &e : Edges){
        link(e);
    }
    
    printf("%d\n",ans);
}

 

위의 코드에서 각 그룹의 크기를 나타내는 sz 배열은 여기서는 필요없지만 수행 시간에 있어서는  대체로 이득이 된다.

 

 

2. Prim Algorithm

C++ 이 제공하는 priority_queue 를 사용하면,

알고리즘 교과서에서 보는 pseudo code 와는 조금 다르게 구현되기 때문에 몇 자 적는다.

(기회되면 꼼꼼하게 정리하자.)

 

보통 교과서에서 사용되는 Min Heap 은 갱신되는 값을 내부 노드에 반영하는데 반해서,

priority_queue 는 갱신된 값을 새로운 노드로 만들어서 입력한다.

따라서 pop 된 값을 처리하는 과정에서 Prim 알고리즘과 Dijstra 알고리즘에서 차이가 발생한다.

 

일단 코드를 보자.

아래 코드에서 비용을 저장하는 cst 배열은 없어도 동작한다.

그럼에도 굳이 집어넣은 이유는 마지막 부분에서 간략히 언급한다.

 

#include<bits/stdc++.h>

using namespace std;

const int Inf=1e9;
struct edge{
    int to, cst;
};

int sz;
vector<vector<edge>> adj;
vector<int> cst;
vector<bool> vst;

struct info{
    int cst, id;
    bool operator<(const info &rhs) const{
        return cst > rhs.cst;
    }
};

void link(int u,int v,int c){
    adj[u].push_back({v,c});
    adj[v].push_back({u,c});
}

void solve(){
    cst=vector<int>(sz,Inf);
    vst=vector<bool>(sz,false);
    cst[1]=0;
    priority_queue<info> pq;
    pq.push({0,1});
    
    int ans=0;
    while(!pq.empty()){
        info tInfo=pq.top();
        pq.pop();
        int cur=tInfo.id;
        
        if(vst[cur]) continue;
        ans+=tInfo.cst;
        vst[cur]=true;
        
        for(int i=0;i<adj[cur].size();i++){
            edge te=adj[cur][i];
            int nxt=te.to;
            if(!vst[nxt] && cst[nxt]>te.cst){
                cst[nxt]=te.cst;
                pq.push({te.cst,nxt});
            }
        }
    }
    printf("%d\n", ans);
}

int main(){
    int n,m; scanf("%d%d",&n,&m);
    sz=n+1;
    adj=vector<vector<edge>>(sz);
    for(int i=0;i<m;i++){
        int u,v,c; scanf("%d%d%d",&u,&v,&c);
        link(u,v,c);
    }
    solve();
}

 

위의 코드에서 이미 처리가 끝난 정점에 대해서는 visit 배열에 기록한다.

 

 

위의 이미지에서 !vst[nxt] 는 비슷한 Dijkstra 에서는 필요가 없다.

뒤따르는 부등식에 경로의 길이이므로 진행할 수록 점점 더 값이 커져서 자연스럽게 걸러진다.

즉, Dijkstra 에서는 vst 배열 자체가 불필요하다.

 

그러나 Prim 알고리즘에서는 처리된 정점들과 연결해주는 마지막 간선의 비용들만 남겨두므로,

기존에 처리된 정점까지의 거리가 갱신되는 문제점을 갖게 된다.

 

사실 Prim 알고리즘에서는 vst 배열은 필요하지만 cst 배열이 필요가 없다.

하지만 앞서 말한 것처럼 cst 배열을 사용하는 것이 대체로 더 빠르게 처리된다.

C++ 의 priority_queue 의 특징 때문인데,

기존 값을 변경하는 것이 아니라 새 값을 추가한다고 말했다.  

이로 인해 불필요한 정보들이 cst 배열을 쓰지않으면 priority_queue 에 추가된다.

 

교과서 priority_queue 와 Min Heap 과의 차이를 정확히 이해하자.