백준 1922

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

1922번: 네트워크 연결

최소 스패닝 트리 (MST, Minimum Spanning Tree)

① 프림 알고리즘 (노드 기준)

② 크루스칼 알고리즘 (엣지 기준)

 

필요한 자료구조

1. 벡터: 그래프 저장 (인접 리스트)

2. 배열: 방문 여부 체크 (visited)

3. 우선순위 큐: 목적지 노드, 가중치 저장

 

012345678

#include <iostream>
#include <vector>
#include <queue>
#define pii pair<int, int>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n, m, visited[1001], ans;
vector<vector<pii> > v;
struct cmp {
    bool operator()(pii a, pii b) {
        return a.second > b.second;
    }
};
priority_queue<pii, vector<pii>, cmp> pq;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    v.resize(n + 1);
    rep(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
    }
 
    pq.push({ 1,0 });
    while (!pq.empty()) {
        int dst = pq.top().first;
        int weight = pq.top().second;
        pq.pop();
 
        if (visited[dst]) continue;
        visited[dst] = 1;
        ans += weight;
        for (pii p : v[dst]) {
            pq.push(p);
        }
    }
    cout << ans;
}