백준 2660번 : 회장뽑기 java

이 문제는 각각의 회원들을 bfs를 이용해서 조사하면서 다른 회원들과 몇 번의 연결을 통해서 전부 연결되는지 확인하는 문제입니다.

이 문제에서 모든 회원들이 자신의 친구 즉 한 번의 연결만으로 연결된다면 1점을 가지게 됩니다.

그리고 모든 회원들이 자신의 친구이거나 친구의 친구일 경우 2점을 가지게 되며 가장 점수가 낮은 사람이 회장이 된다고 합니다.

따라서 모든 회원들이 점수를 몇 점을 가지는지 검사해주고 점수가 가장 낮은 사람의 점수와 후보의 수, 그 후보의 번호를 출력하면 됩니다.

---

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

public class Main {
    static int N;
    static List<List<Integer>> l = new ArrayList<>();
    static int[] point;
    static int minPoint = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        point = new int[N+1];
        for(int i = 0; i<=N; i++)
            l.add(new ArrayList<>());

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

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            if(A == -1 && B == -1)
                break;

            l.get(A).add(B);
            l.get(B).add(A);
        }

        bfs();

        int cnt = 0;
        for(int i = 1; i<=N; i++){
            if(point[i] == minPoint)
                cnt++;
        }

        System.out.println(minPoint + " "+ cnt);
        for(int i = 1; i<=N; i++)
            if(point[i] == minPoint)
                System.out.print(i+" ");
        System.out.println();
    }

    static void bfs(){
        for(int i = 1; i<=N; i++){
            int val = bfs(i);

            point[i] = val;
            minPoint = Math.min(minPoint, val);
        }
    }

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

        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(v, 0));
        visited[v] = true;
        int cnt = 0;

        while(!q.isEmpty()){
            Node vertex = q.poll();

            for(int i = 0; i<l.get(vertex.v).size(); i++){
                int nextV = l.get(vertex.v).get(i);

                if(visited[nextV])
                    continue;

                visited[nextV] = true;
                q.offer(new Node(nextV, vertex.cnt+1));
            }

            cnt = vertex.cnt;
        }

        return cnt;
    }
}
class Node{
    int v, cnt;

    Node(int v, int cnt){
        this.v = v;
        this.cnt = cnt;
    }
}

위에서 말씀드린대로 각각의 후보를 bfs를 이용하여 조사하여 조건에 맞게 출력하였습니다.