[ BOJ 백준 1647번 - 도시 분할 계획 ] 해설 및 코드

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

목적

마을을 두개로 분리하는데, 각 마을 안에서 임의의 두 집은 경로가 존재하여야 한다. 마을에 적어도 집이 한개는 있어야 한다.

 

접근법

1. MST 를 구하는 문제이다. 크루스칼 알고리즘을 적용하되, 간선을 n-2개만 만든다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
const int N = 1e5, M = 1e6;
int p[N+1];
struct edge{
    int a,b,c;
    bool operator<(const edge& oth)const{
        return c<oth.c;
    }
}ed[M];
 
int find(int x){
    return p[x]<0?x:p[x]=find(p[x]);
}
        
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        
    int n,m;cin>>n>>m;
    memset(p,-1,sizeof(int)*(n+1));
    f(i,0,m)cin>>ed[i].a>>ed[i].b>>ed[i].c;
    sort(ed,ed+m);
 
    int ans=0,cnt=0;
    f(i,0,m){
        int ra=find(ed[i].a),rb=find(ed[i].b);
        if(ra==rb)continue;
        ans+=ed[i].c;
        p[ra]=rb;
        if(++cnt==n-2)break;
    }
    cout<<ans;
        
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.