💛V [백준 2660/C++] 회장뽑기

문제

BOJ 링크

풀이

플로이드-워셜 알고리즘을 활용해 각 노드의 친구 관계를 구할 수 있다.

친구 관계는 최댓값을 점수로 매기므로, 출발 노드를 기준으로 최대 가중치를 구한다.

이후 다른 노드 점수와 비교해 최소 점수를 가진 노드를 배열에 저장한다.

후기

이전 문제에서는 플로이드 워셜 그래프를 구하고, 정답용 배열을 계산하는 과정에서 자기 자신에 대한 가중치를 빼주었다.

알고리즘 관련 코드는 해당 구현부에서 모두 마치고, 정답을 계산하는 부분에선 다른 코드들이 침범하지 않도록 init에 자기 자신에 대한 초기화 코드을 추가했다 (17-20번째 줄).

코드

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

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

	// input & init
	int fw[51][51];
	vector<int> v;
	int n;
	cin >> n;

	fill(&fw[0][0], &fw[n][n + 1], 1e9);
	for (int i = 1; i <= n; i++)
	{
		fw[i][i] = 0;
	}

	while (1)
	{
		int a, b;
		cin >> a >> b;

		if (a == -1) break;

		fw[a][b] = 1;
		fw[b][a] = 1;
	}

	// floyd-warshall
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				fw[i][j] = min(fw[i][k] + fw[k][j], fw[i][j]);
			}
		}
	}

	int res = 1e9;
	for (int i = 1; i <= n; i++)
	{
		int score = 0;
		for (int j = 1; j <= n; j++)
		{
			score = max(score, fw[i][j]);
		}

		if (score > res) continue;
		else if (score < res)
		{
			res = score;
			v.clear();
		}
		v.push_back(i);
	}

	// output
	cout << res << " " << v.size() << "\n";
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}

	return 0;
}

결과