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

(Briefing)
(문제)	(단 하나의 맥락)	(입출력과 되어야 하는 그림)
임의의 두 사람이 최소 몇 단계만에 이어질 수 있는지 계산하는 게임 케빈 베이컨 수 : 모든 사람과 케빈 베이컨 게임을 했을 때 나오는 단계의 합	특정 노드에서 나머지 모든 노드까지 최소 거리의 합(가중치는 모두 1)	I // 유저 수 N - 친구 관계 수 M (1) 친구 관계 A - B ... (M) 친구 관계 A' - B' O // 케빈 베이컨 수가 가장 작은 사람 번호 출력 (여려명일 때는 번호가 가장 작은 사람 출력)

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

public class Main {

    // Input Supply Cable
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    // point recognition
    static int N, M;
    static int distance[][];

    public static void main(String[] args) throws IOException {

        // Input Supply Cable
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // Preprocessing
        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] = 10000001;
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            distance[s][e] = 1;
            distance[e][s] = 1;
        }

        // Operating floyd - warshall
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; k <= N; k++) {
                    if (distance[i][j] > distance[i][k] + distance[k][j])
                        distance[i][j] = distance[i][k] + distance[k][j];
                }
            }
        }

        // Operating Sum
        int Min = Integer.MAX_VALUE;
        int Answer = -1;
        for (int i = 1; i <= N; i++) {
            int plate = 0;
            for (int j = 1; j <= N; j++) {
                plate = plate + distance[i][j];
            }
            if (plate < Min) {
                Min = plate;
                Answer = i;
            }
        }

        // Output Extracting Cable
        System.out.println(Answer);
    }
}