[백준 2660] 회장뽑기 (C++)

문제를 보면 알겠지만, 그래프 문제이다.

회원의 점수는 자신을 제외한 회원들까지의 최단거리를 계산했을 때, 최댓값이 된다.

따라서, 모든 회원이 친구면 점수가 1이고, 모든 회원이 친구 혹은 친구의 친구면 최단거리의 최댓값이 2이므로 점수는 2가 된다.

따라서, 그래프를 표현하고 bfs로 각 회원까지의 최단 거리를 계산하여 점수를 구할 수 있다.

이 점수가 최소인 사람이 회장이 되고, 회장이 될 수 있는 사람들을 모두 찾아줘야 하므로, 모든 정점에서 bfs를 해서 점수를 구해야한다.

bfs를 해서 점수를 모두 구한 뒤에, 최소 점수와 회장 후보를 결정할 수도 있지만, bfs를 돌면서 결정하는 것이 메모리 관점에서 효율적이다.

방법은 각 정점에서 bfs를 진행하면서 최솟값 mn을 갱신해간다. 만약, mn과 해당 정점에서의 점수가 동일하면, 회장 후보에 추가한다.

또, 최솟값이 새롭게 갱신된다면, 회장 후보를 비우고 최솟값에 대응되는 정점을 회장 후보에 추가한다.

이를 코드로 옮기면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

const int NOT_VISITED = -1;

int n, mn = 0x7f7f7f7f;
vector<int> adj[51];
vector<int> candidates;

void bfs(int st) {
	queue<int> q;
	int vis[51] = {}, score = 0;
	fill(vis, vis + n + 1, NOT_VISITED);

	q.push(st);
	vis[st] = 0;

	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		for (int nxt : adj[cur]) {
			if (vis[nxt] != NOT_VISITED) continue;
			q.push(nxt);
			vis[nxt] = vis[cur] + 1;
			score = max(score, vis[nxt]);
		}
	}

	if (score == mn) candidates.push_back(st);
	else if (score < mn) {
		mn = score;
		candidates.clear();
		candidates.push_back(st);
	}
}

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

	cin >> n;
	while (1) {
		int u, v;
		cin >> u >> v;
		if (u == -1 && v == -1) break;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) bfs(i);
	cout << mn << " " << candidates.size() << "\n";
	for (int c : candidates) cout << c << " ";
}