[JUNGOL-1060]최소비용신장트리(MST)

최소비용신장트리 (MST)를 하려면 내가 학습해본 알고리즘은 

1. 프림알고리즘 (Prim's Algorithm)

2. 크루스칼알고리즘 (Kruskal's Algorithm)

이 두가지를 보았다.

1. 프림 알고리즘은 

 1) 구성 그래프가 주어질 때, 임의의 정점(Vertex or node) 를 정한다.

 2) 우선순위큐(Min heap)에 1)에서 선택한 정점을 넣는다.

 3) 큐에서 비용이 최소인 간선정보를 뽑아낸다.

 4) 해당 간선정보의 도착 정점이 연결되지 않았다면 연결 시키고, 방문처리한다. 

 5) 해당 도착정점의 간선정보를 큐에 넣는다.

 6) 큐가 비어질 때 까지 3)~5) 과정을 반복한다. 

2. ...

이 문제는 프림알고리즘을 이해하고 풀이해보았다. 

// MST
#include<cstdio>
#include<vector>
#include<queue>
#include<functional>
#include<utility>
#define mp(a,b) make_pair(a,b) 
using namespace std;
 
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<bool> VB;
typedef pair<int,int> pii;
typedef vector<pii> VP;
typedef vector<VP> VVP;
 
 
VVP G;
VB vis;
 
priority_queue<pii, vector<pii>, greater<pii>> Q;
 
int main(){
    int n; scanf("%d", &n);
    G.resize(n+1);
    vis = VB(n+1, false);
    
    for(int s = 1 ; s <= n ; s++){
        for(int e = 1 ; e <= n ; e++){
            int cost = 0;
            scanf("%d", &cost);
            if(cost!=0){
                G[s].push_back(mp(cost, e));
            }
        }
    } // graph input ; Indirected Graph
    
    int ans = 0;
    Q.push(mp(-1,1)); // pair<int, int> = cost, finish_vertex
    vis[1] = true;
    while(!Q.empty()){
        pii here = Q.top();
        Q.pop();
        
        if(!vis[here.second]){
            vis[here.second] = true;
            ans += here.first;
        }
        
        for(auto iter = G[here.second].begin() ; iter != G[here.second].end() ; iter++){
            pii there = *iter;
            int edge_cost = there.first;
            int edge_there= there.second;
            if(!vis[edge_there]){
                Q.push(mp(edge_cost, edge_there));
            }
        }
    }
    
    printf("%d", ans);
    return 0;
}