BOJ 1647번 : 도시 분할 계획

간선의 cost 합을 최소화 하고, 각 집 사이에 경로가 항상 존재해야 한다는 조건이므로 MST를 사용하는 문제이다.

https://00rigin.tistory.com/59

MST (Minimum Spanning Tree) 최소 신장 트리

단, 조건은 마을을 2개로 만들면서, 도로의 유지비를 최소화 해야하는 것이다.

따라서, MST로 마을을 재구성 한 후에, 가장 도로 유지비가 비싼 집 하나를 정하고, 그 집을 2번째 마을로 설정한다.

이렇게 할 경우, 두개의 마을이 생기면서 가장 비싼 도로가 하나 사라져 문제의 조건을 만족 할 수 있다.

 

<소스코드>

#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<bitset>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
struct edge{
    int a;
    int b;
    int c;
};
 
int n,m;
vector<edge> v;
 
bool operator < (edge a, edge b){ // 우리가 만든 struct를 사용하는 템플릿에 대해 대소 비교를 하기 위해서 오버로딩
    if(a.c < b.c){
        return true;
    }
    else{
        return false;
    }
}
 
int parent[100001]; // 대장 내 노드의 대장을 저장함.
// parent[2] = 1 , Parent[3] = 1 이면 노드 1,2,3은 같은 그래프
 
int get_pa(int x){
    if(parent[x] == x){ // 내가 대장
        return x;
    }
    else{ // 내가 대장이 아닐 경우 재귀 돌아서 대장을 찾을때 까지 가서 대장을 찾음.
        parent[x] = get_pa(parent[x]); // 이렇게 안할 경우 같은 그래프임에도 대장이 다를 수 있음. 중요한 부분.
        // 재귀로 여기서 덮어 씌워놔야 다른 곳에서 재귀를 계속 안돌고 적은 시간내에 덮어쓴 값을 바탕으로 빠르게 대장 을 알 수 있음
        return parent[x];
        
        // return get_pa(parent[x]);
        // 이렇게 할 경우 시간초과가 남.
    }
}
 
void Union(int a, int b){ // 대장을 작은 놈으로 바꿔줘서 가은 그래프로 보이게 함
    
    if(a<b){
        parent[b] = a;
    }
    else{
        parent[a] = b;
    }
}
 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin>>n>>m;
    
    for(int i = 1; i<=n; i++){
        parent[i] = i;
    }
    
    for(int i = 0; i<m; i++){
        int a,b,c;
        cin>>a>>b>>c;
        edge e;
        e.a = a;
        e.b = b;
        e.c = c;
        v.push_back(e);
    }
    
    sort(v.begin(), v.end());
    
    int ans = 0;
    int las = 0;
    for(int i = 0; i<m; i++){
        int a,b,c;
        a = v[i].a;
        b = v[i].b;
        c = v[i].c;
        
        int ap = get_pa(a);
        int bp = get_pa(b);
        if(ap!=bp){ //a와 b가 같은 그래프가 아니면
            ans+=c;
            Union(ap,bp); // 하나의 그래프로 합쳐줌
            las = c;
        }
    }
    ans = ans - las;
    cout<<ans<<endl;
}
 

<문제>

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

1647번: 도시 분할 계획