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

문제

접근 방법

백준에서 제목이 곧 답인 문제 중 하나이다.
최소 신장 트리에 대한 코드를 작성할 수 있으면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int V, E, sum = 0;
    cin >> V >> E;
    vector<bool> visted(V + 1);
    vector<vector<pair<int, int>>> map(V + 1, vector<pair<int, int>>());
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    while (E--)
    {
        int A, B, C;
        cin >> A >> B >> C;
        map[A].push_back({B, C});
        map[B].push_back({A, C});
    }
    pq.push({0, 1});
    while (!pq.empty())
    {
        auto cur = pq.top();
        pq.pop();
        if (visted[cur.second])
            continue;
        visted[cur.second] = true;
        sum += cur.first;
        for (auto next : map[cur.second])
        {
            if (visted[next.first])
                continue;
            pq.push({next.second, next.first});
        }
    }
    cout << sum;
    return 0;
}

풀이

프림 알고리즘을 적용하여 풀었다. 이외에도 크루스칼 알고리즘이 존재한다. 크루스칼은 선택한 선이 사이클인지 확인하며 풀어줘야 할 것이다.