[JAVA]백준_1389_케빈 베이컨의 6단계 법칙

문제링크

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

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

플로이드 알고리즘을 적용하는 문제이다.

문제를 자세히 읽어보면 케빈베이컨의 수가 가장 작은 사람을 구하는 것인데

케빈베이컨의 수의 플로이드알고리즘을 적용하여 최단 거리를 구한 거리의 합을 의미한다.

위의 예제를 플로이드 알고리즘을 적용하여 돌리면

0	2	1	1	2
2	0	1	2	3
1	1	0	1	2
1	2	1	0	1
2	3	2	1	0

의 결과가 나오는데 가로행의 값을 다 더한 결과 중 최소값을 출력하면 된다.

 

package BOJ;

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

public class Main_1389 {
    static int INF = 999999999;
    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 map[][] = new int[N+1][N+1];
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(i!=j) map[i][j] = INF;
            }
        }

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            // A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a][b] = 1;
            map[b][a] = 1;
        }

        for(int k=1;k<=N;k++){
            for(int i=1;i<=N;i++){
                for(int j=1;j<=N;j++){
                    map[i][j] = Math.min(map[i][j],map[i][k]+map[k][j]);
                }
            }
        }

        int min = Integer.MAX_VALUE;
        int minIdx = 0;

        for(int i=1;i<=N;i++){
            int sum = 0;
            for(int j=1;j<=N;j++) sum +=map[i][j];

            if(min>sum){
                min = sum;
                minIdx = i;
            }
        }

        System.out.println(minIdx);
    }
}