BOJ : 2660 회장뽑기

---

[BOJ 2660(G5)리뷰]

주어진 관계를 이용해 BFS를 수행해 DEPTH를 기록하여 해결할 수 있는 문제다.
플로이드 문제를 풀려고 봤는데 BFS로 푸는게 더 간단할 것 같아 BFS로 풀었다.

주의해야 할 조건은 회원 사이에 친구를 통해서 모든 회원을 알 수 있다는 점이다. 즉, 각각의 회원은 자신을 제외한 모든 회원간의 DEPTH가 반드시 존재한다.

따라서 BFS를 돌며 각 회원간의 DEPTH를 기록하면 된다. 점수가 1점이라는 의미는 모든 회원간의 DEPTH가 1이라는 의미이고, 점수가 2점이라는 의미는 모든 회원 중 최대 깊이의 DEPTH가 2라는 의미이다.

그래서 나는 크게 '1. BFS를통해 회원간 DEPTH계산, 2.각 사람별 최대 DEPTH를 통한 점수계산 3.점수 중 최소값 계산하여 후보 선정'의 과정을 거쳤다.

후보가 중복될 수 있으므로, 최소값을 미리 계산후 최소값에 해당하는 후보들을 벡터에 넣어 출력했다.

/*
	21.02.06
	BOJ : 2660 회장뽑기 (https://www.acmicpc.net/problem/2660)
	BFS
*/
#include <bits/stdc++.h>

using namespace std;

#define MAX 1e9

int n;
int adj[51][51];
int dist[51][51];
int score[51];

void init() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dist[i][j] = MAX;
		}
	}
}

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

	while (true) {
		int a, b;
		cin >> a >> b;
		if (a == -1 && b == -1) break;
		adj[a][b] = 1;
		adj[b][a] = 1;
	}

	init();

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i==j || !adj[i][j]) continue;
			queue<pair<int, int>> q;
			q.push({ j,1 });
			while (!q.empty()) {
				auto cur = q.front(); q.pop();
				if (cur.second > dist[i][cur.first] || cur.first == i) continue;
				dist[i][cur.first] = cur.second;

				for (int k = 1; k <= n; k++) {
					if (adj[cur.first][k]) {
						q.push({ k,cur.second + 1 });
					}
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		int mx = 0;
		for (int j = 1; j <= n; j++) {
			if (dist[i][j] == MAX) continue;
			mx = max(mx, dist[i][j]);
		}
		score[i] = mx;
	}

	int mn = MAX;
	for (int i = 1; i <= n; i++) {
		mn = min(score[i], mn);
	}

	vector<int>ans;
	for (int i = 1; i <= n; i++) {
		if (score[i] == mn) ans.push_back(i);
	}

	cout << mn << " " << ans.size() << '\n';
	for (auto v : ans) {
		cout << v << " ";
	}

	
	return 0;
}