[백준 1647] 도시 분할 계획 C++

문제

백준 1647 도시 분할 계획 C++

1647번: 도시 분할 계획

풀이

최소 스패닝 트리를 이용한다.

1. 엣지들을 가중치에 대해 오름차순으로 정렬해주고

2. 최소 스패닝 트리를 만족하도록 가중치가 낮은 n - 2개의 엣지를 연결하면 두 그룹으로 나뉘게 된다.

3. 지금까지의 가중치의 합(ans)가 정답이 된다.

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int Parent[100001];
 
struct Edge
{
    int u;
    int v;
    int weight;
};
 
int Find(int x)
{
    if (Parent[x] == x)
        return x;
    else
        return Parent[x] = Find(Parent[x]);
}
 
void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
    if (x != y)
        Parent[y] = x;
}
 
bool IsSameParent(int x, int y)
{
    x = Find(x);
    y = Find(y);
    if (x != y)
        return false;
    else
        return true;
}
 
int myCompare(Edge& a, Edge& b)
{
    return a.weight < b.weight;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
 
    vector<Edge> v;
    int N, M, cnt;
    long long ans = 0;
    cin >> N >> M;
    cnt = N - 2;
 
    for (int i = 1; i <= N; i++)
    {
        Parent[i] = i;
    }
 
    int a, b, cost;
 
    for (int i = 0; i < M; i++)
    {
        cin >> a >> b >> cost;
        v.push_back({ a, b, cost });
    }
 
    sort(v.begin(), v.end(), myCompare);
 
    for (int i = 0; i < v.size(); i++)
    {
        if (IsSameParent(v[i].u, v[i].v) == false)
        {
            cnt -= 1;
            if (cnt < 0)
                break;
 
            Union(v[i].u, v[i].v);
            ans += v[i].weight;
        }
    }
 
    cout << ans;
    return 0;
}