[ BOJ 백준 2406번 - 안정적인 네트워크 ] 해설 및 코드

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

 

 

목적

최소 비용으로 회사의 네트워크가 안정적이 되도록 만들자.

 

접근법

1. MST를 구하는 문제이다. 크루스칼 알고리즘을 적용하자.

2. 모든 지사들은 1번 본사와 연결되어 있다. 고로 본사와의 연결은 배제시키자.

3. 따라서 지사들을 n-2개의 간선으로 연결하면 된다.

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
const int N=1001;
 
struct edge{
    int a,b,c;
    bool operator<(const edge& oth)const{
        return c<oth.c;
    }
}ed[N*N];
int p[N],ans[N][2];
 
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;
    int cnt=0;
    memset(p,-1,sizeof(p));
    while(m--){
        int a,b;cin>>a>>b;
        int ra=find(a),rb=find(b);
        if(ra==rb)continue;
        p[ra]=rb;
        ++cnt;
    }
    m=0;
    f(i,1,n)f(j,1,n){
        int c;cin>>c;
        if(j==1||j>i||find(i)==find(j))continue;
        ed[++m].a=i;
        ed[m].b=j;
        ed[m].c=c;
    }
    sort(ed+1,ed+1+m);
        
    int x=0,k=0;
    f(i,1,m){
        if(cnt+k>=n-2)
            break;
        int ra=find(ed[i].a),rb=find(ed[i].b);
        if(ra==rb)continue;
        p[ra]=rb;
        ans[++k][0]=ed[i].a;
        ans[k][1]=ed[i].b;
        x+=ed[i].c;
    }
    cout<<x<<' '<<k<<'\n';
    f(i,1,k) cout<<ans[i][0]<<' '<<ans[i][1]<<'\n';
    
    return 0;
}
 

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

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