BOJ 2660 회장뽑기

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

/***
 * 시간제한: 1초, 메모리제한: 128MB
 * 회원수 1 <= N <= 50, 연결 수는: N*(N-1)/2 = 49*25= 약 1200.
 * 아이디어: 각 회원을 기준으로 bfs를 수행해서 점수를 계산하여 저장한 후, 점수가 가장 좋은 사람의 값을 찾고, 동일한 점수를 가진 사람을 리스트로 뽑는다.
 */
public class Main {
    static int N;
    static int[] costs;
    static List<List<Integer>> list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        list = new ArrayList<>();

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

        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            if(from == -1 || to == -1) break;

            list.get(from).add(to);
            list.get(to).add(from);
        }

        costs = new int[N+1];
        for(int i=1; i<=N; i++){
            bfs(i);
        }

        // 회장 후보 점수 찾기.
        int minCost = Integer.MAX_VALUE;
        for(int i=1; i<=N; i++){
            minCost = Math.min(minCost, costs[i]);
        }

        // 회장 후보의 후보 찾기
        List<Integer> cntList = new ArrayList<>();
        for(int i=1; i<=N; i++){
            if(costs[i] == minCost) cntList.add(i);
        }

        Collections.sort(cntList);

        System.out.println(minCost+" "+cntList.size());
        for(Integer num : cntList){
            System.out.print(num+ " ");
        }
    }

    static void bfs(int startV){
        boolean[] visited = new boolean[N+1];
        visited[startV] = true;

        int cost = 0;
        int maxCost = 0;
        Deque<int[] > queue = new ArrayDeque<>();
        queue.offer(new int[]{startV, cost});

        while(!queue.isEmpty()){
            int[] curr = queue.poll();

            int currV = curr[0];
            int currCost = curr[1];

            for(Integer nextV : list.get(currV)){
                if(!visited[nextV]){
                    visited[nextV] = true;
                    maxCost = Math.max(maxCost, currCost+1);
                    queue.offer(new int[] {nextV, currCost+1});
                }
            }
        }
        costs[startV] = maxCost;
    }
}