<링크>

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<intint>> adj[1001];
priority_queue<pair<intint>> 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<intint> 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의 맨위에는 현재 갈수있는 가장 가까운 정점이 떠올라와있기 때문에 선택하고, 해당 노드로 인해 추가되는 간선들을 다시 큐에 넣어주면 된다.


+ Recent posts