백준 1922 : 네트워크 연결

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

MST(최소스패닝트리)의 가장 기초 문제이다.

kruskal 알고리즘 대신 prim 알고리즘을 이용해서 풀어보았다.

kruskal 알고리즘은 작은 간선들 부터 차례로 확인해보면서

그 간선을 연결하면 cycle이 도는지 확인하는 알고리즘이다.

이 때 union-find를 사용하여 재귀적으로 각 정점의 뿌리정점을 정의해주어

서로가 연결되어있는지의 여부를 확인한다.

반면, prim 알고리즘은 한 정점을 기준으로 최소 간선을 따라

다음 정점를 탐색해나간다. 정점을 하나씩 탐색할때마다

새로 탐색한 정점에 연결되어 있던 유효한 간선들을 priority_queue에 넣는다.

이는 한정점을 탐색하고 다음 최소 간선은 priority_queue에 넣어놓은 top() 을

빼서 쓰면 된다. 이때 유효한 간선들이란 해당 간선이 이어져있는 정점이

방문하지 않은 정점일 때다. 따라서 visited[] 배열을 설정하여 cycle 을 미연에

방지하기 때문에 따로 cycle 여부를 확인해줄 필요는 없다.

priority_queue를 사용했을때 시간복잡도는 kruskal 이나 prim 모두 ElogV 로 같다.

(E는 간선, V는 정점)

※ 참고로 pair 를 사용할때

만약 pair가 한가지 용도로만 쓰이지 않는다면 first, second가 헷갈릴때가 있다.

이때 define을 통해 pair자체의 이름과 first, second를 정의해주면 코드짤 때 덜 헷갈린다

나는 여기서 

pair : line

first : weight

second : index(간선이 향하고 있는 정점의 번호)

로 정의해주었다.

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 41 42 43 44 45 46 47 48 49 50

#include <iostream> #include <vector> #include <queue> #include <algorithm> #define MAX 1001 #define line pair<int, int> #define weight first #define idx second using namespace std; int n, m; vector<line> com[MAX]; bool visited[MAX] = {false, }; priority_queue<line, vector<line>, greater<line>> pq; int cost = 0; void prim(int init){ visited[init] = true; for(line pa : com[init]){ pq.push(pa); } while(!pq.empty()){ line curEdge = pq.top(); pq.pop(); if(visited[curEdge.idx]) continue; visited[curEdge.idx] = true; cost += curEdge.weight; for(line pa : com[curEdge.idx]){ if(!visited[pa.idx]){ pq.push(pa); } } } cout << cost << endl; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; while(m--){ int u, v, weight; cin >> u >> v >> weight; com[u].push_back(make_pair(weight, v)); com[v].push_back(make_pair(weight, u)); } prim(1); return 0; }