백준 1197번: 최소 스패닝 트리(프림 알고리즘)

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

1197번: 최소 스패닝 트리

 

이 문제는 최소신장 트리 이다.

최소 신장 트리는 크루스칼 알고리즘과 프림 알고리즘으로 풀 수 있는데

나는 BFS에 우선순위 큐만 더하면 된다고 생각해서 프림 알고리즘으로 풀었다.

프림 알고리즘은  간단하게  시작 노드에서 가중치가 작은 간선을 이어가며 구하는 것이다.

크루스칼 알고리즘은 사이클이 생성되지 않게 작은 가중치를 가진 간선을 연결하는 것이다.

코드를 보자

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int v,e;
long long ans;
bool visit[10001];
vector<pair<int,int>> node[10001];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
int main(){
    cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
    cin >>v>>e;
    for(int i=0;i<e;i++){
        int a,b,c;
        cin>>a>>b>>c;
        node[a].push_back({b,c});
        node[b].push_back({a,c});
    }
    pq.push({0,1}); //가중치, 노드
    while(!pq.empty()){
        int w=pq.top().first;
        int next=pq.top().second;
        pq.pop();
        if(visit[next]) continue;
        visit[next]=true;
        ans+=w;
        for(int i=0;i<node[next].size();i++){
            int nextw=node[next][i].second;
            int nextnode=node[next][i].first;
            pq.push({nextw,nextnode});
        }
    }
    cout <<ans;
}