백준 1647 도시 분할 계획 (c++)

1647번: 도시 분할 계획

최소 스패닝 트리를 이용한 문제이다. 문제는 간단하다. 크루스칼 알고리즘을 통해 최소 가중치를 가지는 트리 경로를 구한 후 이를 다시 정렬하여 가중치가 가장 큰 값을 뺀 값을 출력해주었다.
어렵지 않게 풀 수 있었다. 다만 최소 스패닝 트리를 사용한다는 것을 떠올리는데 시간이 오래 걸렸다. 주어진 노드들 간의 최소로 하는 어떤 것을 구하는 문제라면 최소 스패닝 트리를 떠올리도록 하자.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, result = 0;
vector<pair<int, pair<int, int>>> v;
vector<pair<int, pair<int, int>>> road;
int p[100001];

int findParent(int a) {
    if (a == p[a]) return a;
    else return p[a] = findParent(p[a]);
}

void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);

    if (a != b) p[a] = b;
}

bool sameParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);

    if (a == b) return true;
    else return false;
}

void solution() {
    for (int i = 1; i <= N; i++) {
        p[i] = i;
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < v.size(); i++) {
        int a = v[i].second.first;
        int b = v[i].second.second;
        int c = v[i].first;

        if (!sameParent(a, b)) {
            unionParent(a, b);
            road.push_back(v[i]);
            result += c;
        }
    }

    sort(road.begin(), road.end());

    result -= road.back().first;

    cout << result;
}

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

    cin >> N >> M;

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

    solution();

    return 0;
}```