C++ 백준 2660 회장뽑기

백준 2660

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

2660번: 회장뽑기

풀이 전 나의 생각

월드컵 축구의 응원을 위한 모임의 친구 관계가 그래프의 형태로 주어진다.

어떤 회원이 다른 모든 회원과 친구, 친구의 친구, 친구의 친구의 친구... 의 조건에 따라

점수가 주어지질 때 회장이 될 수 있는 후보 점수와 후보의 수, 후보를 구해야한다.

 

조건

- 회원의 수는 50명을 넘지 않는다. 

- 마지막 줄에는 -1이 두 개 들어있다.

 

과정

이 문제는 결국 주어진 친구 관계의 그래프를 모두 탐색했을 때

나올 수 있는 최소 탐색 횟수를 구하는 문제다.

 

1 - 2 - 3 의 그래프가 있고, 1과 3이 친구 관계라고 가정할 때,

1 부터 3까지 차례대로 가는지, 아니면 1에서 바로 3으로 가는지

분기를 나누어 최소 탐색 횟수를 구할 수 있기 때문에 

플로이드 - 워셜 알고리즘을 사용하여 풀 수 있다.

 

하지만 BFS로도 충분히 풀 수 있는 문제기 때문에 

현재 풀이는 BFS를 사용하여 진행했다.

 

왜냐하면 결국 BFS도 최소 거리를 탐색하는 알고리즘이기 때문이다.

 

따라서 현재 노드와 관련있는 노드를 탐색할 때마다 점수를 증가시켜주며

노드의 끝까지 BFS를 진행하면 답을 쉽게 구할 수 있다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

vector<vector<int>> link(51);
bool visited[51];
int candidate[51];

// 친구 관계를 탐색하며 최소 후보 점수를 구해준다.
int bfs(int st)
{
	fill(visited, visited + 51, false);

	visited[st] = true;
	queue<pair<int, int>> q;
	int ans = 0;

	q.push(make_pair(st, 0));

	while (!q.empty())
	{
		int now_st = q.front().first;
		int now_score = q.front().second;
		q.pop();
		
		if (ans < now_score) ans = now_score;
	
		for (int next : link[now_st])
		{
			if (!visited[next])
			{
				visited[next] = true;
				q.push(make_pair(next, now_score + 1));
			}
		}
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, MIN = INT_MAX, minScoreCandidates = 1;
	
	cin >> N;

	// 탐색을 위한 친구 관계 정보를 저장한다.
	while (true)
	{
		int u, v;
		cin >> u >> v;

		if (u == -1 && v == -1) break;

		link[u].push_back(v);
		link[v].push_back(u);
	}

	// 후보 점수의 최소값과 최소 점수 후보의 수를 구한다.
	for (int i = 1; i <= N; i++)
	{
		int score = bfs(i);
		candidate[i] = score;
		
		if (MIN > score)
		{
			minScoreCandidates = 1;
			MIN = score;
		}
		else if (MIN == score)
		{
			minScoreCandidates++;
		}
	}

	cout << MIN << " " << minScoreCandidates << '\n';

	// 최소 점수와 같은 후보를 오름차순으로 출력한다.
	for (int i = 1; i <= N; i++)
	{
		if (MIN == candidate[i])
		{
			cout << i << " ";
		}
	}
}