[백준] 회장뽑기

백준 온라인 저지의 2660번 회장뽑기 문제 입니다.

문제 출처

회장뽑기

문제 해설

문제로 주어지는 것은 각 회원들의 관계도다. 회원이 다른 회원과 연결되어 있는 거리가 얼마이냐에 따라서 답이 정해진다. 그렇기 때문에

• 그래프로 입력을 받아서 회원과의 연결을 구성한다.
  • 두 회원 중 한명만 다른 한명을 아는 경우는 없음으로, 연결되는 방향은 양방향이다.
• 특정 회원을 중심으로, 다른 친구와의 거리를 알아야 하기 때문에 BFS를 사용한다.
  • 모든 회원을 대상으로 BFS를 시도한 다음에, 최대 거리가 가장 작은 회원들이 회장 후보이다.
• 시간복잡도는 n명의 회원을 대상으로 BFS를 시도함으로 시간복잡도는 O(n(n+e))이다.
  • n은 50밖에 되지 않음으로, 충분히 작동할 수 있다.

위의 정보를 토대로 코딩해보자.

#include <bits/stdc++.h>

using namespace std;

vector<int> graph[51];
int depth[51];
bool check[51];

int BFS(int _start) {
	queue<int> iQ;
	iQ.push(_start);
	int resultNum = 0;
	while (!iQ.empty()) {
		int cur = iQ.front(); iQ.pop();
		check[cur] = true;
		for (auto nxt : graph[cur]) {
			if (check[nxt]) continue;
			iQ.push(nxt);
			if(depth[nxt] ==0) depth[nxt] = depth[cur] + 1;
			if (depth[nxt] > resultNum) resultNum = depth[nxt];
		}
	}

	return resultNum;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n; cin >> n;
	while (true) {
		int num1, num2; cin >> num1 >> num2;
		if (num1 == -1) break;
		graph[num1].push_back(num2);
		graph[num2].push_back(num1);
	}

	int result[51];
	int minNum = 51;
	for (int i = 1; i < n + 1; ++i) {
		fill(depth, depth + 51, 0);
		fill(check, check + 51, false);
		result[i] = BFS(i);
		if (result[i] < minNum) minNum = result[i];
	}
	
	vector<int> resultList;
	for (int i = 1; i < n + 1; ++i) {
		if (result[i] == minNum) resultList.push_back(i);
	}

	cout << minNum << " " << resultList.size()<<"\n";
	for (auto cur : resultList)
		cout << cur << " ";

	return 0;
}