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

걍 BFS인데 조금 헤맸다. 모든 노드에 대해서 BFS를 각각 실행하고, 각 노드간의 최소 거리를 계산한 후 더해주는 계산이 필요하다.

마지막으로, 가장 최소값인 노드(겹칠 경우, 가장 작은 숫자를 가진 노드번호)를 출력한다.

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

public class Main {

    static int N;
    static boolean[] check;
    static int min = Integer.MAX_VALUE;
    static int result = 0;
    static ArrayList<ArrayList<Integer>> arr;

    private static void BFS(int i) {
        Queue<Integer> queue = new LinkedList<>();
        check = new boolean[N + 1];
        check[i] = true;
        queue.offer(i);
        int sum_value = 1;
        int sum = 0;
        while (!queue.isEmpty()) {
            int len = queue.size();
            for(int j=0; j<len; j++) {
                int tmp = queue.poll();
                for (int x : arr.get(tmp)) {
                    if (!check[x]) {
                        check[x] = true;
                        queue.offer(x);
                        sum += sum_value;
                    }
                }
            }
            sum_value ++;
        }
        //sum이 더 작을경우에만 갱신한다. 이렇게 하면, 최소 노드가 유지된다.
        if(min > sum) {
            result = i;
            min = sum;
        }
    }

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

        arr = new ArrayList<>();

        for (int i = 0; i <= N; i++) {
            arr.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr.get(a).add(b);
            arr.get(b).add(a);
        }

        for(int i=1; i<=N; i++) {
            BFS(i);
        }
        System.out.println(result);
    }
}