플로이드 와샬에 대한 정리는 이 글을 참고하자.

'케빈 베이컨의 6단계 법칙'

BOJ '케빈 베이컨의 6단계 법칙'

풀이 코드

배열을 처음 생성하면 0으로 초기화가 된다.
이 경우 사람 사이의 가장 가까운 연결 관계를 찾기 위해 min 메서드를 효과적으로 사용하기 어려워지므로 매우 큰 값으로 초기화하는 것이 중요했다.

#include <iostream>
using namespace std;
#define INF 987654321;
int N,M;
int friends[105][105];

int main() {

    // 1. 입력하기
    cin >> N >> M;

    // friends 배열 초기화
    for(int i=0;i<=N;i++){
        for(int j=0;j<=N;j++){
            friends[i][j] = INF;
        }
    }
    
    for(int i=0;i<M;i++){
        int A, B;
        cin >> A >> B;
        friends[A][B] = 1;
        friends[B][A] = 1;
    }
    

    // 2. 모든 경우의 케빈 베이컨 수를 파악한다.
    for(int k=1;k<=N;k++){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(i == j) continue;
                // 연결 단계 업데이트
                if(friends[i][k] > 0 && friends[k][j] > 0){ // 연결되어 있다면
                    friends[i][j] = min(friends[i][j], friends[i][k] + friends[k][j]);
                }
            }
        }
    }

    
    // 3. 정답 계산 후 출력
    pair<int,int> answer={0, 987654321} ;
    for(int i=1;i<=N;i++){
        int sum =0;
        for(int j=1;j<=N;j++){
            if(i == j) continue;
            sum+=friends[i][j];
        }
        if(sum < answer.second){
            answer = {i, sum};
        }
    }

    cout << answer.first;
}