[ BOJ 백준 2610번 - 회의준비 ] 해설 및 코드

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

목적

필요한 위원회의 개수와, 각 위원회에서 누가 대표로 선정돼야 하는지 구하자.

 

접근법

1. 알고있는 사람끼리 같은 위원회에 속해야 한다. 따라서 k는 알고있는 사람 네트워크의 개수라고 할 수 있다.

2. 각 위원회의 대표는 네트워크의 중간에 있어야 한다. (가장 먼 사람과의 거리가 최소가 되어야 하므로...)

3. 플로이드 와샬 알고리즘을 적용하여 각 노드간 최단 거리를 구하고, 각 위원회의 대표를 정해서 오름차순으로 정렬한다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
const int INF=101;
int n,m,cnt[101]{},s[101][101];
bool vis[101]{};
 
int sol(int i){
    int mn=INF,ret;
    f(j,1,n)if(s[i][j]!=INF){
        vis[j]=true;
        int tmp=0;
        f(k,1,n)if(s[j][k]!=INF&&tmp<s[j][k])tmp=s[j][k];
        if(mn>tmp){
            mn=tmp;
            ret=j;
        }
    }
    return ret;
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    f(i,1,n){
        s[i][i]=0;
        f(j,i+1,n)s[i][j]=s[j][i]=INF;
    }
    while(m--){
        int a,b;cin>>a>>b;
        s[a][b]=s[b][a]=1;
    }
    
    f(k,1,n)f(i,1,n)f(j,i+1,n)if(s[i][k]!=INF&&s[k][j]!=INF){
        int tmp=s[i][k]+s[k][j];
        if(s[i][j]>tmp)s[i][j]=s[j][i]=tmp;
    }
    
    int k=0,ans[101];
    f(i,1,n)if(!vis[i])ans[++k] = sol(i);
    cout<<k<<'\n';
    sort(ans+1,ans+k+1);
    f(i,1,k)cout<<ans[i]<<'\n';
    
    return 0;
}
 

 

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

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