[백준] 도시 분할 계획

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

우선 문제부터 간단하게 요약하면,

 

N개의 마을과 그 마을들을 연결하는 M개의 길이 있을 때, 마을을 두 그룹으로 나누고, 그 안에서 필요하지 않은 길을 모두 없앨 때, 길의 유지비 합을 최소로 할 때의 유지비를 구해야 하는 문제입니다. 

 

문제를 직접 한번 읽어보는 것이 정확합니다.

 

<Solution>

우선 문제를 읽자마자 최소 신장 트리가 생각이 납니다. 그러면 최소 신장트리를 구성해서 그 중 가장 비용이 큰 길 하나를 제외하면 되지 않을까? 라는 생각이 듭니다. 

 

실제로 이렇게 문제를 해결하면 되는데, 여기서 조금 고민했던 점은, 최소가 아닌 신장트리에서도 가장 큰 길이를 빼게 되면, 이런 경우가 더 최소가 되는 경우가 생길 수 있지 않을까? 라는 부분입니다. 

 

하지만 Kruskal 등의 알고리즘의 진행 과정을 생각해보면, 중간에도 마을들의 집합들이 계속 생기게 되는데 이런 마을들의 집합 각각이 최소로 이어져 있을 것을 알 수 있기 때문에 위와 같은 알고리즘으로 문제를 해결해도 되는 것을 알 수 있습니다. (즉 Kruskal 알고리즘이 진행되는 동안 unionset으로 묶이는 마을들도 해당 마을들 끼리의 최소 스패닝트리)

 

실제 구현은 아래 문제와 거의 유사하게 구현하였습니다. 

 

https://life318.tistory.com/238

[백준] 최소 스패닝 트리

 

#include <iostream>
#include <algorithm>

using namespace std;

int N, M;

struct edge{
    int s,d,cost;
};

edge edges[1000000+10];

int parent[1000000+10];

bool Comp(const edge &e1, const edge &e2){
    return e1.cost < e2.cost;
}

int findParent(int n){
    if(parent[n] != n){
        parent[n] = findParent(parent[n]);
    }
    return parent[n];
}

void unionSet(int v1, int v2){
    int p1 = findParent(v1);
    int p2 = findParent(v2);
    
    if(p1 > p2){
        parent[p1] = p2;
    }
    else{
        parent[p2] = p1;
    }
}

int main(){
    int ans = 0;
    int max_c = -1;

    cin >> N >> M;

    for(int i = 0; i < M; i++){
        cin >> edges[i].s >> edges[i].d >> edges[i].cost;
    }

    // sort edges by cost
    sort(edges, edges+M, Comp);

    // initialize parent array
    for(int i = 0; i<=N; i++){
        parent[i] = i;
    }

    // looking for each edges, do Kruskal MST algorithm
    for(int i = 0; i<M; i++){
        edge* cur_e = edges+i;
        // if it doesn't make cycle, insert it in set
        if(findParent(cur_e->s) != findParent(cur_e->d)){
            unionSet(cur_e->s, cur_e->d);
            ans += cur_e->cost;
            max_c = max(max_c, cur_e->cost);
        }

    }

    cout << ans - max_c << endl;
    return 0;
}