백준 1647 도시 분할 계획 : 전형적인 MST + 부모 동일 유무 파악시 주의할 점

문제 링크

www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

풀이 아이디어

오랜만에 mst(minimum spanning tree) 문제를 풀어보았다.

MST의 구현 방법의 기본은 union find 이므로 반드시 union find(disjoint set) --> MST 순서대로 공부할 것.

그러면 내가 코드에 쓴 find(),union() 함수의 의미를 알 것이다.

알 것이라 가정하고,

문제는 각 edge의 cost 값의 합을 최소로 하도록 마을을 2개로 쪼개는 것이므로,

'하나의 MST를 만든 후 가장 cost가 큰 edge 하나 빼기' 방식으로 풀 수 있다.

하나 주의해야 할 점이, 아래 내가 주석으로 달아 놨듯이

union을 확인할 때 parent[first]!=parent[second] 이딴식으로 확인하면 안되고

반드시 find(first)!=find(second)로 확인을 해야한다는 것이다.

업데이트가 안된 상태로 부모노드를 확인하면 (즉 parent[]로 확인 시)

부모노드가 실제로 같을 경우에도 다르다고 인식이 되어 cost 계산에 쓸데 없는 값이 추가되어 

답이 틀려질 수가 있다.

 

이점만 유의하면 풀 수 있는 문제.

코드

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<pair<int,pair<int,int>>> v;
int parent[100001];
vector<int> cost;
int ans;

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

void un(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;
    parent[y]=x;

}

int main(void){
    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;
        v.push_back({c,{a,b}});
    }
    sort(v.begin(),v.end());
    for(int i=0; i<v.size(); i++){
        int first = v[i].second.first;
        int second = v[i].second.second;
        if(find(first)!=find(second)){ //union을 시켜줘야 한다. 주의할 점은 부모 같은지 여부를 반드시 find()로 확인할것!!!
            un(first,second);
            cost.push_back(v[i].first);
        }
    }
    for(int i=0; i<cost.size()-1; i++){
        ans += cost[i];
    }
    cout<<ans;

}