[백준 2660] 회장 뽑기

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int arr[52][52];
int ans[52];
int n,a,b,temp,result,minTot=99999999,cnt;
int main(void){
    scanf("%d", &n);
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i!=j)
                arr[i][j]=99999999;
        }
    }
    
    while(scanf("%d %d", &a, &b)==2){
        if(a==-1 && b==-1)
            break;
        else {
            arr[a][b]=1;
            arr[b][a]=1;
        }
    }
    
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(arr[i][j]>arr[i][k]+arr[k][j])
                    arr[i][j]=arr[i][k]+arr[k][j];
            }
        }
    }
    
    for(int i=1; i<=n; i++){
        temp=0;
        for(int j=1; j<=n; j++){
            if(arr[i][j]>temp)
                temp=arr[i][j];
        }
        if(temp<minTot){
            minTot=temp;
            cnt=1;
            ans[cnt]=i;
        } else if(temp==minTot){
            cnt++;
            ans[cnt]=i;
        }
    }
 
    sort(ans+1,ans+cnt+1);
 
    printf("%d %d\n", minTot, cnt);
    for(int i=1; i<=cnt; i++)
        printf("%d ", ans[i]);
    
    return 0;
}

 

바로 직전에 푼 1389 케빈 베이컨~ 문제랑 매우 비슷하다.

그래도 조금 헷갈릴 수 있어서 (사실 내가 헷갈림) 그림으로 정리했다.

 

플로이드 와샬 알고리즘에 따라서 회원 수와, 친구인 회원번호들을 입력한 후 배열을 보면 위 사진이다.

 

 

플로이드 와샬 알고리즘을 적용하면 위와 같다.

배열을 보면 arr[from][to]로 볼 때 from에서 to까지의 간선 갯수임을 알 수 있다. 

 

문제에서 원하는 회장후보의 점수가 가장 낮다는 것은 모든 정점들과 연결되었을 때 얼마나 최소의 개수로 연결할 수 있냐는거다.

이걸로 문제 풀면 된다.