[백준]1389.케빈 베이컨의 6단계 법칙

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

 

www.acmicpc.net

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


public class Main {
    static int N, M;
    static ArrayList<Integer>[] arrayLists;
    static int[] ans;
    static boolean[] visit;
    static int[] dist;


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


        ans = new int[N + 1];


        arrayLists = new ArrayList[N + 1];
        for (int i = 1; i < N + 1; i++) {
            arrayLists[i] = new ArrayList<>();
        }


        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());


            arrayLists[a].add(b);
            arrayLists[b].add(a);
        }



        for (int i = 1; i < N + 1; i++) {
            visit = new boolean[N + 1];
            visit[i] = true;


            dist = new int[N + 1];
            DFS(i, 0);
//            for (int j = 1; j < N + 1; j++) {
//                System.out.print(dist[j] + " ");
//            }
//            System.out.println();
            ans[i] = getKevin_Bacon();
        }


//        System.out.println();
//        for (int i = 1; i < N + 1; i++) {
//            System.out.print(ans[i] + " ");
//        }


        System.out.println(getMinKevinBaconIdx());



    }


    static int getKevin_Bacon() {
        int sum = 0;
        for (int val : dist) {
            sum += val;
        }
        return sum;
    }


    static void DFS(int start, int depth) {
        if (dist[start] != 0) {
            dist[start] = Math.min(dist[start], depth);
        } else {
            dist[start] = depth;
        }


        for (int i = 0; i < arrayLists[start].size(); i++) {
            int next = arrayLists[start].get(i);
            if (!visit[next]) {
                visit[next] = true;
                DFS(next, depth + 1);
                visit[next] = false;
            }
        }
    }


    static int getMinKevinBaconIdx() {
        int idx = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < N + 1; i++) {
            if (ans[i] < min) {
                idx = i;
                min = ans[i];
            }
        }


        return idx;
    }
}