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

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

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

 

 

풀이 :

플로이드 와샬 알고리즘을 사용하여 풀이하였습니다.

다익스트라 알고리즘이 찾고자 하는 노드의 경로를 찾는 알고리즘이었다면, 플로이드 와샬 알고리즘은 모든 노드에 대한 경로를 찾는 알고리즘으로 삼중 for문을 사용하여 구현할 수 있습니다.

 

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int n, t;
    static ArrayList<ArrayList<Integer>> map = new ArrayList<>();
    static int[][] distance;
    static int min = Integer.MAX_VALUE;
    static final int INF = 987654321;


    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());
        t = Integer.parseInt(st.nextToken());

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

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i == j) distance[i][j] = 0;
                else distance[i][j] = INF;
            }
        }


        for(int k = 0; k < t; k++){
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            distance[a][b] = distance[b][a] = 1;
        }

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

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

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                result[i] += distance[i][j];
            }
        }

        int num = 0;

        for(int i = 1; i <= n; i++){
            if(min > result[i]){
                min = result[i];
                num = i;
            }
        }

        System.out.println(num);
    }
}