[BOJ] 1197. 최소 스패닝 트리 (C++)

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 찾고 가중치를 출력하기

주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리

생각할 것

최소 스패닝 트리 문제이므로 크루스칼이나 프림 알고리즘 이용하기

코드

1. 크루스칼 알고리즘

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

using namespace std;

struct Edge {
    int start, end, cost;
};

struct cmp {
    bool operator()(Edge &e1, Edge &e2) {
        return e1.cost > e2.cost; // 오름차순
    }
};

int find(int a, vector<int> &parent) { 
    if (parent[a] == a) return a;
    return parent[a] = find(parent[a], parent);
}

void merge(int a, int b, vector<int> &parent) { // &를 안붙여서 합병이 일어나지 않아 틀렸었다..!
    int pa = find(parent[a], parent);
    int pb = find(parent[b], parent);
    parent[pa] = pb;
}

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

    int V, E, A, B, C;
    cin >> V >> E;

    priority_queue<Edge, vector<Edge>, cmp> pq;
    for (int i = 0; i < E; i++) {
        cin >> A >> B >> C;
        pq.push(Edge{A, B, C});
    }

    vector<int> parent(V + 1);
    for (int i = 1; i <= V; i++) parent[i] = i;

    int res = 0, count = 0;
    while (count != V - 1) {
        Edge edge = pq.top();
        pq.pop();
        if (find(edge.start, parent) == find(edge.end, parent)) continue;
        merge(edge.start, edge.end, parent);
        res += edge.cost;
        count++;
    }

    cout << res;

    return 0;
}

2. 프림 알고리즘

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

using namespace std;

struct cmp {
    bool operator()(pair<int, int> &p1, pair<int, int> &p2) {
        return p1.second > p2.second; // 오름차순
    }
};

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

    int V, E, A, B, C;
    cin >> V >> E;

    vector<vector<pair<int, int>>> adj(V + 1);
    for (int i = 0; i < E; i++) {
        cin >> A >> B >> C;
        adj[A].push_back({B, C});
        adj[B].push_back({A, C}); // 양방향이므로 두 번 넣어주기
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
    vector<bool> visited(V + 1);

    int res = 0;
    pq.push({1, 0});
    while (!pq.empty()) {
        pair<int, int> cur = pq.top();
        pq.pop();

        if (visited[cur.first]) continue;
        visited[cur.first] = true;
        res += cur.second;

        for (int i = 0; i < adj[cur.first].size(); i++) {
            pq.push(adj[cur.first][i]);
        }
    }

    cout << res;

    return 0;
}