<링크>
https://www.acmicpc.net/problem/1922
<소스코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include<stdio.h> #include<queue> #include<vector> using namespace std; int visit[1001]; vector<pair<int, int>> adj[1001]; priority_queue<pair<int, int>> q;//오는비용,노드 int main() { int N, M; scanf("%d%d", &N, &M); while (M--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); adj[a].push_back({ b,c }); adj[b].push_back({ a,c }); } q.push({ 0,1 }); int ans = 0; while (!q.empty()) { int cost = q.top().first; int node = q.top().second; q.pop(); if (visit[node]) continue; visit[node] = 1; ans += -cost; for (pair<int, int> p : adj[node]) { int toCost = p.second; int toNode = p.first; q.push({ -toCost,toNode }); } } printf("%d", ans); } | cs |
<풀이>
prim알고리즘을 적용했으며 priority_queue를 이용했다.
prim알고리즘은 greedy하게 현재 선택한 노드들에서 퍼져나갈 수 있는 간선들 중 가장 적은 비용의 간선을 택한다.
처음에 {0,1}을 넣어서 1번노드까지가는 비용 0을 넣어놓고
연결되어있으면 다 priority_queue에 넣어준다.
큐에 들어있는 쌍들은 {해당노드까지 가는 비용, 노드}인데 가장 작은값이 맨위에 올라와야하기 때문에 음수를 곱했다.
한번 방문한 노드는 또 볼필요없으므로 visit배열로 체크했다.
priority_queue의 맨위에는 현재 갈수있는 가장 가까운 정점이 떠올라와있기 때문에 선택하고, 해당 노드로 인해 추가되는 간선들을 다시 큐에 넣어주면 된다.