[알고리즘] 백준 2660번: 회장뽑기 (C++)

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

2660번: 회장뽑기

이번 문제의 핵심이 플로이드 와샬이긴 하지만

개인적인 느낌으로는 플로이드 와샬을 끝내고, 회장 후보 수와 회장 후보들을 출력하는 게 더 핵심처럼 와닿았다.

그래서 이번 문제는 '구현' 키워드에 넣어두었다.

 

왜냐하면 이런 식으로 최솟값을 구하고, 그 최솟값을 유발하는 인덱스 or 노드들을 처리하는 방법은 볼 때마다 헷갈렸었기에 이번 기회에 직접 구현해보았다.

 

[구현]

1. score가 나왔을 때, 그것이 새로운 최솟값이면 기존의 최솟값과 바꾸어주고, 그 최솟값을 유발한 인덱스 or 노드들을 없앤다.
2. 기존의 최솟값과 같다면 배열에 넣어준다.

>> 의외로 간단하지만 개인적으로는 볼 때마다 헷갈림을 유발하던 코드다. 이번 기회에 정리 끝!

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

	if (score < scoreResult) {
		scoreResult = score;
		chairman.clear();
		chairman.push_back(i);
	}
	else if (score == scoreResult) {
		chairman.push_back(i);
	}
}

---

[AC 코드]

#include <iostream>
#include <cmath>
#include <vector>
#define MAX 50 + 1
#define INF 987654321
using namespace std;

int cache[MAX][MAX];
int n;

void floydWarshall() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (cache[i][k] != INF && cache[k][j] != INF) {
					cache[i][j] = min(cache[i][j], cache[i][k] + cache[k][j]);
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) cache[i][j] = 0;
		}
	}
}

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

	cin >> n;

	// init
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cache[i][j] = INF;
		}
	}

	while(1){
		int a, b;
		cin >> a >> b;
		if (a == -1 && b == -1) break;
		cache[b][a] = 1;
		cache[a][b] = 1;
	}

	floydWarshall();

	int cnt = 0;
	int score;
	int scoreResult = INF;
	vector<int> chairman;
	for (int i = 1; i <= n; i++) {
		score = 0;
		for (int j = 1; j <= n; j++) {
			score = max(score, cache[i][j]);
		}

		if (score < scoreResult) {
			scoreResult = score;
			chairman.clear();
			chairman.push_back(i);
		}
		else if (score == scoreResult) {
			chairman.push_back(i);
		}
	}

	cout << scoreResult << ' ' << chairman.size() << '\n';
	for (int i = 0; i < chairman.size(); i++) {
		cout << chairman[i] << ' ';
	}

	return 0;
}