백준 [2660] "회장 뽑기"

플로이드-워셜을 통해 해결하는 문제 같지만 BFS를 통해 해결했다. 회장 후보를 알아내야 하기 때문에 모든 인원이 회장후보가 가능한지 부터 시작하였다. 예제에서는 모든 사람이 1개 이상의 관계를 가지고 있는 것 같았지만 혹시나 없을 수도 있기에 만약 SIZE가 0라면 진행하지 않았다.

자신의 인간관계를 거치면서 다녀온 인간관계는 현재 인간관계에서 +1 해주었고 최대 깊이 인간 관계를 계속 업데이트 해줬다.

마지막으로 현재 사람의 인간관계 깊이에 현재 사람 번호를 넣고 최소 인간 관계층을 업데이트 한 후 마지막에 출력해주었다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

struct DATA {
	int cur;
	int floor;
};
vector<int> v[51];
vector<int> result[51];
int n = 0;
int a, b;
bool check[51];

int minfloor = 9999999999;

void solve(int a) {
	memset(check, false, sizeof(check));
	queue<DATA> q;
	int maxfloor = 0;
	q.push({a, 0});

	check[a] = true;

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

		//cout << cur << " " << floor << endl;

		maxfloor = max(maxfloor, floor);

		for (int i = 0; i < v[cur].size(); i++) {
			if (check[v[cur][i]] == false) {
				check[v[cur][i]] = true;
				q.push({ v[cur][i], floor + 1 });
			}
		}
	}
	result[maxfloor].push_back(a);
	minfloor = min(maxfloor, minfloor);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	while (true) {
		cin >> a >> b;
		if (a == -1 && b == -1) {
			break;
		}
		v[a].push_back(b);
		v[b].push_back(a);
	}

	//1~n번째 사람까지의 회장 후보 검사
	for (int i = 1; i <= n; i++) {
		if (v[i].size() == 0) continue;
		solve(i);
	}

	cout << minfloor << " " << result[minfloor].size() << "\n";
	for (int i = 0; i < result[minfloor].size(); i++) {
		cout << result[minfloor][i] << " ";
	}

	return 0;
}