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

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

케빈 베이컨이라는 배우가 영화를 많이 찍은걸로 유명하기 때문에 생긴 놀이라고 한다.

나와 전세계의 어떤 사람이든 6다리만 건녀면 아는 사이라는 이론으로 유명해졌다.

각설하고 문제는 장황하지만 연결고리가 가장 짧은 사람을 출력하면 해결가능한 문제다.

입력 N이 100이기 때문에 플로이드 와샬 알고리즘으로도 해결 가능

import java.util.Arrays;
import java.util.Scanner;
import java.io.IOException;

public class Main {
	static final int INF = 99;
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();

		int[][] F = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (i == j) F[i][i] = 0;
				else F[i][j] = INF;
			}
		}
		for (int i = 0; i < M; i++) {
			int j = sc.nextInt();
			int k = sc.nextInt();
			F[j - 1][k - 1] = F[k - 1][j - 1] = 1;
		}
				
		for (int k = 0; k < N; k++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (F[i][j] > F[i][k]+F[k][j])
						F[i][j] = F[i][k] + F[k][j];
				}
			}
		}		

		int minVal = INF, person = 0; 
	    for (int i = 0; i < N; i++){
	        int sum = 0;  
	        for (int j = 0; j < N; j++){
	            if (F[i][j] != INF) sum += F[i][j];  
	        }
	        if (sum < minVal){
	            minVal = sum; 
	            person = i;  
	        }
	    }
		System.out.println(person+1);
	}
}