백준 BOJ 2660 - 회장뽑기

정올 너무 맵다 ㅗㅜㅑ

 

www.acmicpc.net/problem/2660

2660번: 회장뽑기

 

각 회원들에 대하여 전부 bfs를 돌려본 다음

bfs의 결과 중 최대값이 점수가 된다.

 

#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

vector<int> v[56];
queue<int> q;
int visit[56] = {0};

vector<int> ans;

void bfs(){
	while(!q.empty()){
		int node = q.front();
		q.pop();
		for(int i=0; i<v[node].size(); i++){
			if(!visit[v[node][i]]){
				q.push(v[node][i]);
				visit[v[node][i]] = visit[node]+1;
			}
		}
	}
}

int main(){
	int n,a,b;
	scanf("%d", &n);
	while(1){
		scanf("%d %d", &a, &b);
		if(a<0 || b<0) break;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	int k = 999;
	for(int i=1; i<=n; i++){
		memset(visit, 0, sizeof(visit));
		while(!q.empty()) q.pop();
		q.push(i);
		visit[i] = 1;
		bfs();
		
		int tmp = -1;
		for(int i=1; i<=n; i++) tmp = max(tmp, visit[i]);
		ans.push_back(tmp);
		k = min(k, tmp);
	}
	
	int cnt = 0;
	for(int i=0; i<ans.size(); i++) if(k == ans[i]) cnt++;
	printf("%d %d\n", k-1, cnt);
	for(int i=0; i<ans.size(); i++) if(k == ans[i]) printf("%d ", i+1);
	return 0;
}

visit[i]에 점수를 저장하고, 점수가 가장 작은 사람들의 횟수를 찾고, 출력해준다음

회장후보들을 출력해주면

간단하게 AC.