링크

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

문제

풀이

플로이드 와샬로 풀었다.

각 유저의 모든 유저에 대한 케빈 베이컨 수를 구하고 케빈 베이컨 수의 합이 가장 적은 유저를 구했다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

//1389
public class Main {
    public static final int INF = 10000000;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int m = Integer.parseInt(arr[1]);

        int[][] graph = new int[n+1][n+1];

        for(int i=0;i<graph.length;i++){
            for(int j=0;j<graph.length;j++){
                if(i != j) graph[i][j] = INF;
            }
        }

        for(int i=0;i<m;i++){
            arr = br.readLine().split(" ");
            int a = Integer.parseInt(arr[0]);
            int b = Integer.parseInt(arr[1]);

            graph[a][b] = 1;
            graph[b][a] = 1;

        }


        ployd(graph);

        int[] kevin = new int[graph.length];
        kevin[0] = INF;
        for(int i=1;i<graph.length;i++){
            int sum = 0;
            for(int j=1;j<graph.length;j++){
                sum += graph[i][j];
            }

            kevin[i] = sum;
        }


        int minIdx = 0;
        for(int i=1;i< kevin.length;i++){
            if(kevin[minIdx] > kevin[i]){
                minIdx = i;
            }
        }
        System.out.println(minIdx);

    }

    public static void ployd(int[][] graph){
        for(int k=1;k< graph.length;k++){
            for(int i=1;i<graph.length;i++){
                for(int j=1;j<graph.length;j++){
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
    }

}