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

양방향 그래프의 BFS!!

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

public class Main {
    static List<List<Integer>>  list = new ArrayList<>();
    static Queue<int[]> queue = new LinkedList<>();
    static boolean[] visited ;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer tokenizer = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());
        int M = Integer.parseInt(tokenizer.nextToken());
        visited = new boolean[N + 1];

        list.add(null);
        for (int i = 0; i < N; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < M; i++) {
            tokenizer = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(tokenizer.nextToken());
            int y = Integer.parseInt(tokenizer.nextToken());
            if (!list.get(x).contains(y)) {
                list.get(x).add(y);
            }
            if (!list.get(y).contains(x)) {
                list.get(y).add(x);
            }
        }
        br.close();
        
        int minUser = N + 1;
        int minSum = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {

            queue = new LinkedList<>();
            visited = new boolean[N + 1];
            int sum = bfs(i + 1);
            if (sum < minSum) {
                minSum = sum;
                minUser = i + 1;
            } else if (sum == minSum) {
                minUser = Math.min(minUser, i + 1);
            }
        }

        bw.write(String.valueOf(minUser));
        bw.flush();
        bw.close();
    }

    static int bfs(int index) {
        int sum = 0;
        int depth = 0;
        queue.offer(new int[] {index, depth});
        visited[index] = true;

        while (!queue.isEmpty()) {
            int[] polled = queue.poll();
            int user = polled[0];
            List<Integer> friends = list.get(user);

            for (int i : friends) {
                if (!visited[i]) {
                    sum += polled[1] + 1;
                    visited[i] = true;
                    queue.offer(new int[] {i, polled[1] + 1});
                }
            }
        }
        return sum;
    }
}