[BOJ] 1647. 도시 분할 계획 (C++)

문제

마을은 N개의 집과 M개의 길로 이루어져 있다. 두 개의 분리된 마을로 분할하려고 할 때, 각 분리된 마을 안에 있는 임의의 두 집 사이에는 경로가 항상 존재해야 한다. 나머지 길의 유지비 합의 최솟값은?

생각할 것

• 모든 마을을 최소값으로 연결하고 가장 긴 하나의 길만 분리하자
  • 크루스칼을 N-2번만 실행하기

코드

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

using namespace std;

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

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(a, parent);
    int pb = find(b, parent);
    parent[pb] = pa;
}

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

    int N, M, A, B, C;
    cin >> N >> M;

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

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

    int count = 0;
    int res = 0;
    while (count != N - 2) {
        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;
}