[Baekjoon] 회장뽑기

https://www.acmicpc.net/problem/2660

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

public class Main {
    private static StringBuilder answer = new StringBuilder();
    private static int memberCount, chairmanMinPoint = Integer.MAX_VALUE;

    private static List<Integer>[] adj;
    private static int[] chairmanPoint;

    public static void main(String[] args) throws IOException {
        init();
        sol();
        print();
    }

    private static void sol() {
        for (int i = 1; i <= memberCount; i++) {
            bfs(i);
        }

        // 정답 출력을 위한 가공
        List<Integer> chairmans = new ArrayList<>();

        for (int i = 1; i <= memberCount; i++) {
            if (chairmanPoint[i] == chairmanMinPoint) {
                chairmans.add(i);
            }
        }

        answer.append(chairmanMinPoint).append(" ").append(chairmans.size()).append("\n"

        );
        for (int i : chairmans) {
            answer.append(i).append(" ");
        }
    }

    private static void bfs(int start) {
        boolean[] visited = new boolean[memberCount + 1];
        visited[start] = true;

        Deque<int[]> q = new ArrayDeque<>();

        q.offer(new int[] { start, 0 });

        int currentMemberPoint = Integer.MIN_VALUE;

        while (!q.isEmpty()) {
            int[] arr = q.poll();
            int current = arr[0];
            int point = arr[1];
            currentMemberPoint = Math.max(currentMemberPoint, point);

            for (int next : adj[current]) {
                if (visited[next]) {
                    continue;
                }

                visited[next] = true;
                q.offer(new int[] { next, point + 1 });
            }
        }

        chairmanPoint[start] = currentMemberPoint;
        chairmanMinPoint = Math.min(chairmanMinPoint, currentMemberPoint);
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        memberCount = Integer.parseInt(br.readLine());

        adj = new ArrayList[memberCount + 1];
        chairmanPoint = new int[memberCount + 1];

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

        StringTokenizer st;

        int member1, member2;

        while (true) {
            st = new StringTokenizer(br.readLine());

            member1 = Integer.parseInt(st.nextToken());
            member2 = Integer.parseInt(st.nextToken());

            if (member1 == -1 && member2 == -1) {
                break;
            }

            adj[member1].add(member2);
            adj[member2].add(member1);
        }
    }

    private static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(answer.toString());
        bw.close();
    }
}

주요 개념

• BFS

풀이 방법

• 각 회원간의 친구 정보를 인접리스트 adj로 저장한다.

• 모든 회원에 대해서 탐색을 수행하여 최대 몇명의 친구를 거쳐야 모든 친구에 도달하는지 구한다.