BOJ 2660 : 회장뽑기

#BOJ 2660 : 회장뽑기

2660번: 회장뽑기

#풀이

회원들의 점수를 계산해서 가장 작은 점수를 가진 회원이 회장이 될 수 있다.

 

회원들은 양방향 그래프로 나타낼 수 있으며 인접리스트를 통해 정점들의 연결 관계를 저장하였다.

 

회원들의 점수를 계산하는 방식은 

그래프의 height로 나타 낼 수 있다.

1->2->3 은 점수가 2

 

1->2

1->3

점수가 1 

 

회원의 height가 점수로 나타 낼 수 있다.

 

BFS를 사용하여 구할 수 있다.

 

#코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n;
int member[51];
vector<int> ans;
vector<int> arr[51];
void bfs(int i) {
	int vis[51] = {0,};
	queue<int>q;
	q.push(i);
	while (!q.empty()) {
		int a = q.front(); q.pop();
		for (auto b : arr[a]) {
			if (vis[b] > 0)
				continue;
			vis[b] = vis[a] + 1;
			q.push(b);
		}
	}
	int m_po = 0;
	for (int j = 1; j < 51; j++)
	{
		if (i == j)
			continue;
		if (m_po < vis[j])
			m_po = vis[j];
	}
	member[i] = m_po;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	int num1, num2;
	while (1) {
		cin >> num1 >> num2;
		if (num1 == -1 && num2 == -1)
			break;
		arr[num1].push_back(num2);
		arr[num2].push_back(num1);
	}
	for (int i = 1; i <= n; i++) {
		bfs(i);
	}
	int min_po = 100;
	for (int i = 1; i <= n; i++)
		min_po = min_po > member[i] ? member[i] : min_po;
	for (int i = 1; i <= n; i++)
	{
		if (min_po == member[i]) {
			ans.push_back(i);
		}
	}
	cout << min_po << ' ' << ans.size() << '\n';
	for (auto a : ans)
		cout << a << ' ';
	cout << '\n';
	return 0;
}