[ 백준 / C++ ] 1197 : 최소 스패닝 트리

[ 문제 ]

 

1197번: 최소 스패닝 트리

 

[ 접근방법 ]

 

프림 알고리즘을 활용하여 MST의 총 가중치를 계산하였다.

 

프림 알고리즘은 MST의 시작점을 하나 정하고, MST와 연결된 최소 가중치 간선을 기준으로 확장하는 방식이다.

 

최소 가중치 간선을 선택하는 과정에서 우선순위 큐를 활용하여 시간복잡도를 줄였다.

 

[ 소스코드 ]

 

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

using namespace std;

int v, e;
vector<pair<int, int>> adj[10005];

int prim()
{
    vector<bool> added(v + 1, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    int ret = 0;

    pq.push({0, 1});
    while (!pq.empty())
    {
        auto [weight, p] = pq.top();
        pq.pop();

        if (added[p])
            continue;

        added[p] = true;
        ret += weight;

        for (auto [q, weight] : adj[p])
        {
            if (!added[q])
            {
                pq.push({weight, q});
            }
        }
    }

    return ret;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    cout << prim();

    return 0;
}