백준 1197번 최소 스패닝 트리

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

 

기본적인 최소 스패닝 트리 문제다.

 

크루스칼 알고리즘과 프림 알고리즘 두가지 방법이 있는데 후자의 방법으로 풀이 하였다.

 

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

struct edge{
    int d, w;
    
    // for priority_queue
    bool operator<(const edge& other) const {
        return w > other.w;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int v, e, a, b, c, cnt=1, sum=0;
    cin >> v >> e;
    bool visited[v+1] = {false};
    vector<edge> adj[v+1];
    priority_queue<edge> pq;
    
    // input
    for(int i=0; i<e; i++){
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    
    visited[1] = true;
    for(edge ed : adj[1]) pq.push(ed);
    
    while(cnt < v){
        edge cur = pq.top();
        pq.pop();
        if(visited[cur.d]) continue;

        cnt++;
        visited[cur.d] = true;
        for(edge ed : adj[cur.d]) pq.push(ed);
        sum += cur.w;
    }
    
    cout << sum;
    
    return 0;
}

 

프림 알고리즘

1. 임의의 정점에서 시작하여 연결된 엣지 중 가중치가 가장 작은 엣지 선택

2. 해당 엣지가 연결된 정점을 추가하고, 그 정점에 연결된 엣지 중 가중치가 작은 엣지를 선택하는 과정을 반복