[BFS] 백준 - 2660번: 회장뽑기 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

2660번: 회장뽑기

 

문제는 다음과 같다.

각 노드들이 서로 친구일 경우 이어져있다. 

따라서 위의 예시처럼 친구 관계도를 정리해 보면

친구 관계도)

1번 - 2번

2번 - 1번, 3번, 4번

3번 - 2번, 4번, 5번

4번 - 2번, 3번, 5번

5번 - 3번, 4번

 

이렇게 되어있고 이중에서 회장 후보의 조건은 친구가 제일 많은 사람을 뽑으면 된다.

그래서 회원 점수가 몇 점인지, 몇 명이고 그에 따른 명단을 보여주면 된다.

 

코드

import java.util.*;

public class Main {
    static ArrayList<Integer>[] map;
    static int n;
    static int min;
    static int[] rank;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        map = new ArrayList[n];
        rank = new int[n];
        min = 50;

        for (int i = 0; i < n; i++) {
            map[i] = new ArrayList<>();
        }

        while (true) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            if (a == -1 && b == -1)
                break;

            map[a - 1].add(b - 1);
            map[b - 1].add(a - 1);
        }

        for (int i = 0; i < n; i++) {
            int c = bfs(i);

            rank[i] = c;
            min = Math.min(min, c);
        }

        int count = 0;

        for (int i = 0; i < rank.length; i++) {
            if (rank[i] == min)
                count++;
        }

        System.out.println(min + " " + count);

        for (int i = 0; i < rank.length; i++) {
            if (rank[i] == min)
                System.out.print(i + 1 + " ");
        }
    }

    private static int bfs(int start) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(start, 0));
        boolean[] visit = new boolean[n];
        visit[start] = true;
        int count = 0;

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

            for (int i = 0; i < map[node.x].size(); i++) {
                if (!visit[map[node.x].get(i)]) {
                    q.add(new Node(map[node.x].get(i), node.c + 1));
                    visit[map[node.x].get(i)] = true;
                }
            }
            count = node.c;
        }
        return count;
    }

    static class Node {
        int x;
        int c;

        public Node(int x, int c) {
            this.x = x;
            this.c = c;
        }
    }
}