백준 2660번 <회장 뽑기>

백준 알고리즘 2660번

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

2660번: 회장뽑기

---

2660번

N명의 회원이 있는 모임에서 회장을 선출하려고 한다. 회장을 선출할 때 사용할 점수를 내서 점수가 가장 낮은 사람이 회장이 될 수 있다. 회장 후보의 점수와 후보의 수, 후보들을 구하여라.

점수는 아래와 같이 낸다.

• 어느 회원이 다른 모든 회원과 친구이면 1점.
• 어느 회원이 모든 회원과의 관계가 친구이거나, 친구의 친구 관계이면 2점.
• 어느 회원이 모든 회원과의 관계가 친구이거나, 친구의 친구이거나, 친구의 친구의 친구 관계이면 3점.

 

입력으로 첫 줄에 회원의 수 N이 들어오고 그 다음 줄부터 친구관계가 들어온다.

 

출력으로 첫 줄에 회장 후보의 점수와 후보의 수를 출력하고 그 다음 줄에 후보들을 출력하면 된다. 

---

문제 해결

BFS를 이용하여 문제를 풀었다.

회원의 수 N 이 50밖에 되지 않기 때문에 각 회원마다 BFS를 돌려서 점수가 몇 점인지 구했다.

 

check 함수로 점수를 구한다.

• check 함수는 모든 회원과의 관계를 확인했는지를 의미하는 boolean 배열 chk와 점수를 구하는 회원의 번호 num을 파라미터로 갖는다.
• num과 친구인 회원을 큐에 넣어 시작점으로 활용한다. 큐에 넣을 때 방문을 체크하기 위해 chk 배열의 값을 true로 바꾼다.
• 큐가 빌 때까지 while 문을 돌린다.
• 이때 큐의 크기만큼 for문을 돌려서 같은 관계인 회원들을 볼 수 있다. 
• 즉, 처음 for문으로 큐에서 나오는 회원들은 num과 친구 관계이고, 두 번째 for문에서 큐에서 나오는 회원들은 num과 친구의 친구 관계이고, 세 번째 for문에서 큐에서 나오는 회원들은 num과 친구의 친구의 친구 관계이다.
• 또한 점수가 가장 낮은 후보를 찾기 때문에 현재 점수(score)가 회장 후보의 점수(minScore)보다 크다면 더 이상 볼 필요가 없기 때문에 함수를 빠져나간다.
• while문을 빠져나와서 모든 회원과 관계를 맺었는지 확인하고 그렇지 않다면 함수를 빠져나간다.
• 점수가 가장 낮은 후보를 찾기 때문에 minScore와 answer를 update한다.

---

코드

package boj2660;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;

/*
 * 회원의 최대 수가 50으로 작기 때문에 모든 회원의 점수를 구하여 가장 낮은 점수를 구했다.
 * 점수를 구하는 방법은 BFS를 사용하였다.
 * num과 친구인 회원을 큐에 넣어서 시작점으로 활용한다.
 * 큐의 크기만큼 for문을 돌려서 같은 관계인 회원들을 본다.
 * 이때 점수(score)가 회장 후보의 점수(minScore)보다 크다면 더 이상 볼 필요가 없기 때문에 return -> 가지치기
 * while문이 끝나면 모든 회원과의 관계를 갖는지 확인한다.
 * minScore와 answer를 update한다.
 * */

public class Main {
	static int N, minScore;
	static ArrayList<Integer> answer;
	static ArrayList<Integer>[] friends;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		friends = new ArrayList[N + 1];
		for (int i = 0; i < N + 1; i++) {
			friends[i] = new ArrayList<>();
		}

		String[] inArr = br.readLine().split(" ");
		int a = Integer.parseInt(inArr[0]);
		int b = Integer.parseInt(inArr[1]);
		while (a != -1 && b != -1) {
			friends[a].add(b);
			friends[b].add(a);

			inArr = br.readLine().split(" ");
			a = Integer.parseInt(inArr[0]);
			b = Integer.parseInt(inArr[1]);
		}

		minScore = Integer.MAX_VALUE;
		answer = new ArrayList<>();
		for (int i = 1; i < N + 1; i++) {
			check(new boolean[N + 1], i);
		}
		Collections.sort(answer);
		System.out.println(minScore + " " + answer.size());
		for (int i = 0; i < answer.size(); i++) {
			System.out.print(answer.get(i) + " ");
		}

	}

	public static void check(boolean[] chk, int num) {
		int score = 0;
		chk[num] = true;
		Queue<Integer> queue = new ArrayDeque<>();
		for (int i = 0; i < friends[num].size(); i++) {
			chk[friends[num].get(i)] = true;
			queue.add(friends[num].get(i));
		}

		while (!queue.isEmpty()) {
			int size = queue.size();
			score++;
			if (score > minScore) {
				return;
			}
			for (int i = 0; i < size; i++) {
				int a = queue.poll();
				for (int j = 0; j < friends[a].size(); j++) {
					if (!chk[friends[a].get(j)]) {
						chk[friends[a].get(j)] = true;
						queue.add(friends[a].get(j));
					}
				}
			}
		}

		for (int i = 1; i < N+1; i++) {
			if (!chk[i]) {
				return;
			}
		}

		if (minScore > score) {
			answer = new ArrayList<>();
			answer.add(num);
			minScore = score;
		} else if (minScore == score) {
			answer.add(num);
		}
	}

}

---

결과

---