최소 스패닝 트리 (feat. 백준, 1197번)

최소 스패닝 트리
https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
set<pair<int, int>> arr[10001];
bool visit[10001]{false};
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;  // 간선값, 도착점
long long func(){
    register long long ans = 0;
    q.push(make_pair(0, 1));
    while(!q.empty()){
        register int node1 = q.top().second, node2, dist = q.top().first;
        q.pop();
        if(visit[node1])
            continue;
        visit[node1] = true;
        ans += dist;
        for(auto& v : arr[node1]){
            node2 = v.first;
            dist = v.second;
            q.push(make_pair(dist, node2));
        }
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int V, E;
    cin >> V >> E;
    memset(visit, false, V);
    for(register int e = 0, A, B, C; e < E; ++e)
        cin >> A >> B >> C, arr[A].insert(make_pair(B, C)), arr[B].insert(make_pair(A, C));
    cout << func();
	return 0;
}
// *&)*@*

 

반응형

최소 스패닝 트리 (MST) 는 크루스칼 알고리즘과 프림 알고리즘으로 풀이가 가능합니다.

저는 프림 알고리즘이 익숙하여 위와 같이  풀이하였습니다.

두 알고리즘은 O(logN) 의 시간 복잡도를 갖기 때문에 상황에 따라 효율이 좋은 알고리즘은 구분되지만, 크게 차이나진 않습니다.