백준(BOJ)_최소 스패닝 트리(1197번)_C++

최소 스패닝 트리(MST)를 구하는 문제다.

아니 정확히는 최소 스패닝 트리의 간선들의 가중치의 합을 구하는 문제다.

 

최소 스패닝 트리를 구하는 알고리즘은 많다.

딱 떠오르는 게 크루스칼 알고리즘과 프림 알고리즘이었는데 크루스칼 알고리즘을 사용하려면

부모 노드를 나타내는 자료구조를 만들어야 해서 간단한 프림 알고리즘으로 문제를 풀었다.

 

모든 간선을 확인하는 시간복잡도가 O(v^2)인  프림 알고리즘도 있는데 해당 알고리즘은 시간 초과가 나올 것 같아서

O(e * log v)인 알고리즘으로 구현했다.

 

최소 스패닝 트리의 간선의 개수는 v - 1 개 이지만, 시작을 의미하는 간선을 포함해야 하기 때문에

for문에서 v번 반복한다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int v, e, answer;
vector<pair<int, int>> g[10001];
bool visit[10001];

struct cmp{
    bool operator()(pair<int, int> a, pair<int, int> b){
        return a.second > b.second;
    }
};

int prim(){
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
    q.push({1, 0});
    int min_dist = 0;

    for(int i = 0; i < v; i++){
        int next, next_dist;

        while (!q.empty()){
            next = q.top().first;
            next_dist = q.top().second;
            q.pop();

            if (visit[next] == false)
                break;
        }

        visit[next] = true;
        min_dist += next_dist;
        for(int j = 0; j < g[next].size(); j++)
            q.push({g[next][j]});
    }

    return min_dist;
}

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    //input
    cin >> v >> e;
    for(int i = 0; i < e; i++){
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    //prim algorithm
    answer = prim();

    //output
    cout << answer;
}