1922- 네트워크 연결 C++(MST, prim or kruskal, BFS)

www.acmicpc.net/problem/1922

1922번: 네트워크 연결

최소 스패닝 트리를 만드는 문제이다. MST를 구하는 알고리즘에는 프림, 크루스칼 알고리즘이 있는데, 그 중 정점을 기준으로 최소비용 엣지을 추가해나가며 MST를 만들어나가는 프림 알고리즘을 이용했다.

크루스칼 알고리즘은 간선을 기준으로 사이클이 만들어지는 지 여부를 union-find 알고리즘으로 파악해나가면서 최소비용 엣지을 MST에 추가해 나가는 알고리즘이다. 

priority_queue을 이용해서 특정 노드에서 갈 수 있는 엣지의 최소값을 찾아내고, bfs를 하면서 방문해나간다. 

우선순위 큐를 쓸 때 struct를 heapify할 때는 꼭 대소 비교를 위한 operator를 정의 해둬야 된다. 아래에서는 노드의 가중치를 기준으로 오름차순 정렬이 되므로, pq는 Edge.cost에 대한 최소힙이 된다. 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// MST - prim 알고리즘
struct Edge {
    int to, cost;
    bool operator<(const Edge& other) const {
        // cout << cost << ' ' << other.cost << endl;
        return cost > other.cost;
    }
};

vector<Edge> graph[1001];
vector<bool> visit(1001);
int n, m;  // node, edge

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

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        graph[x].push_back(Edge({y, c}));
        graph[y].push_back(Edge({x, c}));
    }

    priority_queue<Edge> pq;
    visit[1] = true;
    for (Edge e : graph[1]) {
        pq.push(e);
    }

    int ans = 0;
    while (!pq.empty()) {
        Edge e = pq.top();
        pq.pop();

        int x = e.to;
        if (visit[x]) continue;

        visit[x] = true;
        ans += e.cost;
        for (Edge next : graph[x]) {
            pq.push(next);
        }
    }

    cout << ans;
    return 0;
}