[BOJ] 2660.회장 뽑기 (Java, BFS)

 

2660번: 회장뽑기

문제를 처음 봤을 때 이해가 가지 않아서 정리했습니다. 문제 설명을 왜 이렇게 했을까 😞😞

 

문제 이해하기

1. 회장은 점수가 가장 적은 사람이 됩니다.
2. 점수 계산 방법은 다음과 같습니다.
   1점 : A회원이 B회원과 친구 관계 (A-B)
   2점 : A회원이 B회원과 친구 관계이면서, B회원의 친구인 C회원과도 친구 관계 (A-B-C)
   3점 : A회원이 B회원과 친구 관계이면서, B회원의 친구인 C회원과도 친구 관계이면서, C회원의 친구인 D회원과도 친구 관계 (A-B-C-D)
   …
   이런 식으로 관계있는 사람이 많아질 수록 점수도 점점 커집니다.
   ⇒ 회원이 가질 수 있는 점수 중 가장 큰 점수를 회원의 점수로 가집니다.
3. 회원 수는 50명을 넘지 않습니다.
4. 입력 : 첫째 줄 회원 수, 둘째 줄부터 회원들 친구 관계, 마지막 줄은 -1 두 개
5. 출력 : 첫째 줄 회장 후보 점수와 후보 수, 둘째 줄 회장 후보 오름차순

 

예제 살펴보기

예제에 주어진 5명의 회원들의 관계는 아래와 같습니다.

각 관계에 대해 점수로 나타내봅시다.

	1	2	3	4	5
1	0	1	2	2	3
2	1	0	1	1	2
3	2	1	0	1	1
4	2	1	1	0	1
5	3	2	1	1	0

받은 점수의 최고 점수를 계산해보면 아래와 같습니다.

1	2	3	4	5
3	2	2	2	3

여기서 가장 작은 점수는 2점이므로, 회장 후보 점수는 2점이 됩니다. 그리고 회장 후보는 2, 3, 4로 3명입니다.

따라서 아래와 같이 출력됩니다.

2 3 2 3 4

문제 풀어보기

여기서는 너비 우선 탐색으로 풀어볼 예정 (플로이드-워셜로도 풀 수 있음)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int memberNum = input.nextInt() + 1; // 회원 번호가 1번부터 시작하므로 memberNum 을 1개 늘려준다!
        boolean[][] memberRelations = new boolean[memberNum][memberNum];

        while (true) {
            int i = input.nextInt();
            int j = input.nextInt();

            if (i == -1 && j == -1) break;

            memberRelations[i][j] = true;
            memberRelations[j][i] = true;
        }

        solution(memberNum, memberRelations);

    }

    private static void solution(int memberNum, boolean[][] memberRelations) {
        List<Integer> candidates = new ArrayList<>();
        int minScore = Integer.MAX_VALUE;


        // 각 멤버 점수 계산
        for (int i = 1; i < memberNum; i++) {
            int[] scores = new int[memberNum];
            Arrays.fill(scores, -1);
            Queue<Integer> nextMembers = new LinkedList<>();
            nextMembers.add(i);
            scores[i] = 0;

            while (!nextMembers.isEmpty()) {
                int member = nextMembers.poll();

                for (int j = 1; j < memberNum; j++) {
                    if (memberRelations[member][j] && scores[j] < 0) {
                        nextMembers.add(j);
                        scores[j] = scores[member] + 1;
                    }
                }
            }
            int score = Arrays.stream(scores).max().getAsInt();

            if (score > minScore) continue;

            if (score < minScore) {
                minScore = score;
                candidates = new ArrayList<>();

            }
            candidates.add(i);
        }

        Collections.sort(candidates);

        // 결과 출력
        System.out.println(minScore + " " + candidates.size());
        candidates.forEach(candidate -> System.out.print(candidate + " "));
    }
}