[Baekjoon] 2660_회장뽑기

Gold V

문제(출처: https://www.acmicpc.net/problem/2660)

---

< 회장뽑기 >

 

문제 풀이 

 

bfs를 통해 모든 회원의 친구 깊이를 확인하여 점수를 구한다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _2660_ { // 회장뽑기
	static ArrayList<ArrayList<Integer>> list;
	static int score[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		list = new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			list.add(new ArrayList<>());
		}

		int a = -1, b = -1;
		st = new StringTokenizer(bf.readLine());
		while (((a = Integer.parseInt(st.nextToken())) != -1) && ((b = Integer.parseInt(st.nextToken())) != -1)) {
			list.get(a).add(b);
			list.get(b).add(a);
			st = new StringTokenizer(bf.readLine());
		}

		score = new int[n + 1];
		int min = n;

		for (int i = 1; i < n + 1; i++) {
			boolean visited[] = new boolean[n + 1];
			visited[i] = true;
			bfs(i, visited);
			if (min > score[i]) {
				min = score[i];
			}
		}

		int count = 0;
		for (int i = 1; i < n + 1; i++) {
			if (score[i] == min) {
				count += 1;
			}
		}
		bw.write(min + " " + count + "\n");
		for (int i = 1; i < n + 1; i++) {
			if (score[i] == min) {
				bw.write(i + " ");
			}
		}
		bw.flush();
	}

	private static void bfs(int num, boolean visited[]) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { num, 0 });

		while (!queue.isEmpty()) {
			int x[] = queue.poll();
			for (int i = 0; i < list.get(x[0]).size(); i++) {
				if (!visited[list.get(x[0]).get(i)]) {
					visited[list.get(x[0]).get(i)] = true;
					queue.add(new int[] { list.get(x[0]).get(i), x[1] + 1 });
					if (score[num] < x[1] + 1) {
						score[num] = x[1] + 1;
					}
				}
			}
		}
	}
}

변수)
n : 회원의 수
list : 친구 관계
a, b : 두 개의 회원 번호
score : 점수
min : 회장 후보의 점수
visited : 방문 여부
count : 회장 후보의 수

 

회원 번호 두 개를 입력받아 친구 관계를 ArrayList로 저장한다. 모든 회원을 한 번씩 bfs를 호출하여 점수를 구한다.

 

bfs 탐색하면서 아직 방문하지 않은 곳이라면 방문 후 queue에 넣어주며 socre 값을 최댓값으로 업데이트한다. 

 

점수를 다 구했다면 회원 중에서 점수가 가장 작은 것과 후보의 수를 구한 뒤 출력하고, 회장 후보를 순서대로 출력한다.

---

---