[BOJ] 2660 : 회장뽑기 - travelbeeee

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

---

그래프 플로이드와샬

● 회장은 회원들 중에서 가장 점수가 작은 사람입니다.

● 회원의 점수는 다른 회원들까지의 거리(그래프 상의 경로의 길이) 중 가장 긴 값이 됩니다.

즉, 플로이드와샬 알고리즘을 통해 각 노드(회원) 별로 다른 모든 노드와의 거리를 구해서 그 중 가장 큰 값으로 회원의 점수를 지정하고, 각 회원별로 가장 작은 점수를 가진 사람들을 회장 후보로 올리면 됩니다.

#include<iostream>
#include<algorithm>

using namespace std;

const int INF = 9999999;
int N, x, y;
int map[51][51];
bool checkMinScore[51];
int minScore[51];

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

	cin >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			map[i][j] = INF;
	for (int i = 1; i <= N; i++)
		map[i][i] = 0;

	while (1) {
		cin >> x >> y;
		if (x == -1 && y == -1)
			break;
		map[x][y] = map[y][x] = 1;
	}

	for (int k = 1; k <= N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				if (map[i][k] + map[k][j] < map[i][j])
					map[i][j] = map[i][k] + map[k][j];

	int mm = INF;
	for (int i = 1; i <= N; i++) {
		int m = 0;
		for (int j = 1; j <= N; j++) {
			m = max(m, map[i][j]);
		}
		minScore[i] = m;
		mm = min(mm, minScore[i]);
	}

	int cnt = 0;
	for (int i = 1; i <= N; i++)
		if (minScore[i] == mm) {
			cnt++;
		}
	cout << mm << ' ' << cnt << '\n';
	for (int i = 1; i <= N; i++)
		if (minScore[i] == mm) {
			cout << i << ' ';
		}

	return 0;
}

---