(C++) 백준 1197 최소 스패닝 트리

문제 및 풀이

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

최소 스패닝 구현 문제

임의의 한 노드에서 부터 최소 거리의 노드들로 그리디하게 이동하면 최소 스패닝 트리를 찾을 수 있다. (Prime 알고리즘)

우선 순위 큐를 사용하여 간선을 오름차순으로 정렬한 다음 간선 가중치가 작은 노드순으로 확인하며 모든 노드들을 방문하면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAX_NODE=10005;
int V,E;
int A,B,C;
int ans;

typedef pair<int, int> nodes; // (end, weight)

vector<nodes> adj[MAX_NODE];
vector<bool> isSelected(MAX_NODE);

struct cmp{ // weight 가 작은 순으로 sort
    bool operator()(const nodes &a, const nodes &b){
        return a.second>b.second;
    }
};


int main() {

    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin>>V>>E;

    for(int k=0; k<E; k++){
        cin>>A>>B>>C;
        adj[A].emplace_back(B,C);
        adj[B].emplace_back(A,C);
    }

    priority_queue<nodes, vector<nodes>, cmp> pq;
    pq.push({1,0});

    /*
    const int start=1;
    isSelected[start]=true;for(int i=0; i<adj[start].size(); i++){
    pq.push(nodes(adj[start][i].first, adj[start][i].second));
    }*/

    while(!pq.empty()){

        int next = pq.top().first;
        int cost = pq.top().second;
        pq.pop();

        if(isSelected[next]) continue;
        isSelected[next]=true;

        ans+=cost;

        for(int i=0; i<adj[next].size(); i++){
            pq.push(nodes(adj[next][i].first, adj[next][i].second));
        }

    }


    cout<<ans;


}