백준 1647 도시 분할 계획

문제 설명

• 각 집이 최소 하나 이상의 도로로 연결되어 있는 마을이 있다.
• 하나의 마을을 두 개로 나누고 싶다.
• 각 집을 연결하는 도로마다 유지 비용이 드는데 필요한 도로남 선택하여 각 집을 연결하는 비용을 최소화하여 마을 두 개로 나누는 비용을 구하여라
• 하나의 마을의 집은 모두 최소 하나의 도로로 연결되어 있어야 한다. (한 마을 안에서는 모든 집을 갈 수 있어야 한다.)
  문제 링크

문제 접근

• 일단 모든 집을 최소 비용으로 연결하는 것이므로 최소 스패닝 트리에 관한 문제이다.
• 모든 집은 최대 하나의 도로로 연결하는 것이 가장 효율적이므로 모든 집을 하나의 마을로 묶고, 거기서 가장 비싼 도로 하나만 없애면 두 개의 마을을 가장 저렴하게 나누는 방법으로 판단하고 구현했다.

배운점

• 최소 스패닝 트리로 구현하면 각 노드들은 하나의 간선으로 연결된다는 것을 기억해두자.

풀이 코드

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

using namespace std;

vector<tuple<int, int, int> >    input;

int    group[100001];

int find(int a)
{
    if (group[a] == 0)
        return (a);
    group[a] = find(group[a]);
    return (group[a]);
}

bool    uni(int a, int b)
{
    a = find(a);
    b = find(b);
    if (a == b)
        return (false);
    group[b] = a;
    return (true);
}

int main()
{
    int N, M, a, b, c, check;
    int ret = 0;

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>N>>M;
    for (int i = 0; i < M; i++)
    {
        cin>>a>>b>>c;
        input.push_back(tie(c, a, b));
    }
    sort(input.begin(), input.end());
    for (int i = 0; i < M; i++)
    {
        tie(c, a, b) = input[i];
        if (uni(a, b))
        {
            ret += c;
            check = c;
        }
    }
    ret -= check;
    cout<<ret<<endl;
}