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

출처 : https://www.acmicpc.net/problem/2660

풀이 방법

회장을 뽑기 위해선 완전 탐색 + bfs로 풀이하면 된다.

각 사람을 돌아가며 모든 벡터를 초기화 하고 bfs를 진행한 후 가장 작은 점수인 사람을 선택하면 된다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<vector<int>> graph;

int bfs(int start) {
	int ret = 0;
	queue<pair<int, int>> q; 
	q.push(make_pair(start, 0)); // 시작 점 추가하기
	int visited[N+1];
	for (int i = 0;i < N+1;i++) { // 방문 배열 초기화
		visited[i] = 0;
	}
	visited[start] = 1;
	while (!q.empty()){
		int next = q.front().first;
		int c = q.front().second;
		ret = max(c, ret);
		q.pop();
	    for (int i = 0;i < graph[next].size();i++) {
			if (visited[graph[next][i]] == 0) { // 방문하지 않은 경우
				q.push(make_pair(graph[next][i], c+1)); // 다음에 방문으로 추가 
				visited[graph[next][i]] = 1; // 방문으로 처리
			}
		}
		
	}
	return ret;
}

int main(int argc, char* argv[]) {

	cin >> N;
	
	graph.resize(N+1);
	while(true) {
		int a, b;
		cin >> a >> b;
		if (a == -1 && b == -1) {
			break;
		}
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	int ans = 987654321;
	vector<int> house;
	for (int i = 1;i < N+1;i++) {
		int v = bfs(i);
		if (ans > v) {
			house.clear();
			ans = v;
			house.push_back(i);
		}
		else if (ans == v) {
			house.push_back(i);
		}
	}
	
	cout << ans << " " << house.size() << endl;
	for (int i = 0;i < house.size();i++) {
		cout << house[i] << " ";
	}
	return 0;
}