[플로이드 워셜] 케빈 베이컨의 6단계 법칙(백준 1389번, 자바)

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

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

 

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

public class Main_1389_케빈베이컨의6단계법칙 {

	static int N,M;
	static int[][] map,map2;
	static int answer=Integer.MAX_VALUE;
	static int smallIndex=0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		 N = Integer.parseInt(st.nextToken());
		 M = Integer.parseInt(st.nextToken());
		 
		 map=new int[N+1][N+1];
		 map2=new int[N+1][N+1];
		 
		 for(int i=0;i<M;i++) {
			st=new StringTokenizer(br.readLine());
			int x=Integer.parseInt(st.nextToken());
			int y=Integer.parseInt(st.nextToken());
			map[x][y]=1; map[y][x]=1;
			
		 }

		 
		 for(int ii=1;ii<=N;ii++) {
			 
			 for(int i=1;i<=N;i++) {
				for(int j=1;j<=N;j++) {
					if(map[i][ii]>0 && map[ii][j]>0) {
						if(map[i][j]==0) map[i][j]=map[i][ii]+map[ii][j];
						else map[i][j]=Math.min(map[i][j], map[i][ii]+map[ii][j] );
					}
				}
			 }
		 }
		 
		 for(int i=1;i<=N;i++) {
			 int sum=0;
			for(int j=1;j<=N;j++) {
				if(i==j) continue;
				sum+=map[i][j];
			}
			 if(answer>sum) {
				 answer=sum;
				 smallIndex=i;
			 }
		 }
			 System.out.println(smallIndex);
			 
		 }
}