BOJ #1389 - 케빈 베이컨의 6단계 법칙

https://icpc.me/1389

# 문제 분류
최단 경로 찾기 (Floyd-Warshall Algorithm)

풀이 접근 방법 :

 

1. 각각 노드 쌍에 대한 최단 경로를 모두 구해야 하므로 Floyd-Warshall 알고리즘을 사용하자.

2. 회장뽑기@2660 처럼 생각하면 가중치를 통해 서로 얼마나 떨어져있는지(또는 가까운지) 알 수 있다.

3. 한 명에 대한 나머지 사람들의 점수를 모두 합하면 케빈 베이컨 수를 구할 수 있다.

---

케빈 베이컨 수가 같은 경우 인덱스 순으로 먼저인 사람을 출력하라고 했으므로,

그 부분만 신경써서 처리해주면 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
 
using namespace std;
 
int INF = 1e9;
int N, M, a, b, minn = INF, res;
int v[110][110];
 
int main(){
    scanf("%d %d", &N, &M);
 
    for(int i=0; i<110; i++){
        for(int j=0; j<110; j++){
            v[i][j] = INF;
        }
    }
 
    for(int i=0; i<M; i++){
        scanf("%d %d", &a, &b);
        v[a][b] = 1;
        v[b][a] = 1;
    }
 
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            for(int k=1; k<=N; k++){
                v[j][k] = min(v[j][k], v[j][i] + v[i][k]);
            }
        }
    }
 
    for(int i=1; i<=N; i++){
        int cnt = 0;
        for(int j=1; j<=N; j++){
            if(i != j) cnt += v[i][j];
        }
        if(minn > cnt){
            res = i;
            minn = cnt;
        }
    }
 
    printf("%d", res);
 
    return 0;
}