Six Degrees of Kevin Bacon

https://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon

Six Degrees of Kevin Bacon - Wikipedia

Its a game  영화 배우 한 명을 골라서 그 사람과 같은 영화를 출연한 다른 배우를 고르기를 반복하여

Kevin Bacon을 고르게 되는 가장 짧은 경로를 구하는

KEvin Bacon 얼마나 많은 영화에 출연했길래ㅎㅎ 최대 6번만에 그와 엮인다는 가정이있다고 한다.

the film The River Wild that "he had worked with everybody in Hollywood or someone who's worked with them."

허걱!! 최대 6이라는 것은 kevin과의 최단 경로의 거리가 maximum 6라는 의미로 해석할 수 있다

초록색 배우들이 bacon # 1 (pic from wikipedia)

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

1389번: 케빈 베이컨의 6단계 법칙

어떤 사람 i 를 kevin으로 가정하고 다른 모든 사람과의 최단 경로의 합을 케빈 베이컨 수라고 정의하고 있다.

이렇게 다른 모든 사람과의 최단 거리를 구하는 데에 최적인 알고리즘은 플로이드 와샬이며, N이 100이하로 매우 적기 때문에도 그렇게 추론할 수 있다.

#include <iostream>

using namespace std;
int n,m;
int floyd[101][101];
int MAX = 5001;
int ans,sum = 5001;
int main()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i++) for(int j = 1; j<= n ; j++) floyd[i][j] = MAX;
    while(m--){
        int a,b;
        cin>>a>>b;
        floyd[a][b] = floyd[b][a] = 1;
    }
    for(int k=1; k<=n;k++)for(int i = 1; i <= n; i++) for(int j=1; j <= n; j++)  floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j]);
    
    for(int i =1; i<= n; i++){
        int tmp = 0;
        for(int j = 1; j<= n; j++){
            if(i==j) continue;
            tmp += floyd[i][j];
        }
        if(tmp < sum){
            sum = tmp;
            ans = i;
        }
    }
    cout<<ans;
    return 0;
}