[Do It! 코딩테스트 자바편(김종관)] 문제 063(백준 1389번)

느낀점

• 나한테 적당히 풀 만 했던 문제

문제

케빈 베이컨의 6단계 법칙 (백준: 1389번)

풀이

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

public class Main {
    static int n, m;
    static int[][] matrix;

    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());

        matrix = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j)
                    matrix[i][j] = 0;
                else
                    matrix[i][j] = 10000000;
            }
        }

        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            matrix[a][b] = 1;
            matrix[b][a] = 1;
        }

        for (int k = 1; k <= n; k++) {
            for (int s = 1; s <= n; s++) {
                for (int e = 1; e <= n; e++) {
                    matrix[s][e] = Math.min(matrix[s][e], matrix[s][k] + matrix[k][e]);
                }
            }
        }

        int min = Integer.MAX_VALUE;
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            int tmp = 0;
            for (int j = 1; j <= n; j++) {
                tmp += matrix[i][j];
            }
            if (min > tmp) {
                min = tmp;
                answer = i;
            }
        }
        System.out.println(answer);
    }
}