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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[][] dist = new int[N][N];
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				dist[i][j] = 10000;
			}
		}
		int A, B;
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			A = Integer.parseInt(st.nextToken())-1;
			B = Integer.parseInt(st.nextToken())-1;
			dist[A][B] = 1;
			dist[B][A] = 1;
		}
		for(int k=0;k<N;k++) {
			for(int i=0;i<N;i++) {
				for(int j=0;j<N;j++) {
					if(i != j) {
						dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
					}
				}
			}
		}
		int min = Integer.MAX_VALUE;
		int tmp;
		int result = 0;
		for(int i=0;i<N;i++) {
			tmp = 0;
			for(int j=0;j<N;j++) {
				if(i != j) {
					tmp += dist[i][j];
				}
			}
			if(tmp < min) {
				min = tmp;
				result = i+1;
			}
		}
		System.out.println(result);
		br.close();
	}
}

플로이드-워셜 알고리즘을 이용하면 모든 사람의 케빈 베이컨 수를 각각 구할 수 있습니다.

 

가장 처음 사람 수에 맞게 dist배열을 이차원으로 선언하고

M개의 연결 관계에 따라 관계가 있을 경우 거리를 1로 표시합니다.

 

이후 k명의 사람에 대해 i에서 j까지의 거리보다 i에서 k까지의 거리에 k에서 j까지의 거리를 더한 것이 더 작은 지의 여부를 따지면 플로이드-워셜 알고리즘이 적용됩니다.

 

이 경우 자기 자신까지의 거리를 제외한 모든 거리의 합이 케빈 베이컨 수가 됩니다. min값을 계속 갱신하면서 갱신될 경우 해당 사람이 몇 번인지를 기록해주고 마지막에 출력해주면 끝나게 됩니다.

 

이 경우 공간을 아끼기 위해 인덱스를 0부터 사용하고 A와 B를 받을 때 1씩 빼주고 마지막에 결과를 출력할 때 1을 더해줬습니다.