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

1647번: 도시 분할 계획

문제 요약

문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다.

마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.

그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

사용 알고리즘

크루스칼 알고리즘, 그래프

입출력

• 입력: 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)라는 뜻이다. 임의의 두 집 사이에 경로가 항상 존재하는 입력만 주어진다.
• 출력: 첫째 줄에 없애고 남은 길 유지비의 합의 최솟값을 출력한다. ``` 예제1

입력 7 12 1 2 3 1 3 2 3 2 1 2 5 2 3 4 4 7 3 6 5 1 5 1 6 2 6 4 1 6 5 3 4 5 3 6 7 4 출력 8

## 풀이
크루스칼 알고리즘을 활용하는 문제이다. 그냥 크루스칼 알고리즘을 적용한다면 모든 길이 이어져 분할 할 수가 없게 된다. 크루스칼 알고리즘은 가장 가중치가 작은 길부터 이어나가기 때문에 크루스칼 알고리즘을 한칸 앞에서 끊는다면 문제를 풀 수 있다.

## 어려웠던 점
정점의 개수가 V개 이면 최소 신장 트리의 간선 개수는 V-1이 되고, 이문제는 간선 하나를 제외해야하므로 V-2만큼 반복하면 된다.

## 배운 점 / 느낀 점
1197을 풀고 바로 이를 활용하는 문제가 나왔다. 어렵지 않게 풀 수 있어 크루스칼 알고리즘을 완벽하게 파악하고 있구나 생각하여 좋았다.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int v, e, a, b, c;
vector<pair<int, pair<int, int>>> edges;
vector<int> parent;

int find(int k){
    if(parent[k] == k){
        return k;
    }
    parent[k] = find(parent[k]);
    return parent[k];
}

bool uni(int k, int j){
    k = find(k);
    j = find(j);
    if(k!=j){
        parent[k] = j;
        return true;
    }
    else{
        return false;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    edges = vector<pair<int, pair<int, int>>>();

    int s = 0;

    cin >> v >> e;
    parent = vector<int>(v+1);
    for (int i = 1; i < v+1; i++) {
        parent[i] = i;
    }

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

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

    int i = 0;
    for (int j = 0; j < v-2; j++) {
        while(true){
            a = edges[i].second.first;
            b = edges[i].second.second;
            c = edges[i].first;

            i++;
            if(uni(a,b)){
                s += c;
                break;
            }
            else{
                continue;
            }
        }
    }
    cout << s;
    return 0;
}