백준, BOJ, 1197번, 최소 스패닝 트리 : C++ [CPP] ★★★★★

실제로  MST, 최소 신장 트리를 구현하면 된다.

나는 Prim 알고리즘을 썼다.

 

 

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

1197번: 최소 스패닝 트리

---

 

#맞는 풀이

#include <iostream>
#include <queue>
#include <functional>

#define MAX 10005

using namespace std;
using ti3 = tuple<int,int,int>;

int v,e; // 정점, 간선 개수

vector<pair<int,int>> adj[MAX]; //인접 행렬
bool check[MAX]; //MST에 쓰인지

long long Prim(){
    int cnt = 0; //초기 간선 개수
    long long tot = 0; //MST의 비용
    
    priority_queue<ti3, vector<ti3>, greater<ti3>> heap;
    for(auto next : adj[1]){
        heap.push({next.first, 1, next.second});
    }
    check[1] = 1;
    
    while(1){
        int cost, v1, v2;
        tie(cost, v1, v2) = heap.top();
        heap.pop();
        if(check[v2])continue;
        
        check[v2] = 1;
        cnt++;
        tot += cost;
        if(cnt == v-1) break;
        for(auto next : adj[v2]){
            if(check[next.second])continue;
            heap.push({next.first, v1, next.second});
        }
    }
    
    
    
    
    return tot;
}

int main(){
    cin >> v >> e;
    for(int i = 0; i<e; i++){
        int from, to, cost;
        cin >> from >> to >> cost;
        adj[from].push_back({cost, to});
        adj[to].push_back({cost, from});
    }
    
    long long ans = Prim();
    
    cout << ans;
    
    return 0;
}

 

Kruskal과 Union Find를 같이 알아보면 좋다.