[C++] 백준 2660 : 회장뽑기

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

2660번: 회장뽑기

백준 2660번 회장뽑기를 풀었다.

 

N이 50이하이고 모든 노드 간의 거리를 구해야해서 플로이드 와샬 알고리즘을 사용했다.

회원의 친구 관계를 모두 입력받고 플로이드 와샬 알고리즘을 수행하면 모든 노드 사이의 친구 관계가 구해진다.

조건문을 잘 설정해서 문제에서 요구하는 출력 값을 추가하면 된다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;

#define INF 1000

int dist[51][51];
int arr[51][51];

int main() {
	int n;
	cin >> n;
	while (1) {
		int a, b;
		cin >> a >> b;
		if (a == -1 && b == -1)
			break;

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

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				dist[i][j] = 0;
			else if (arr[i][j] != 0) {
				dist[i][j] = arr[i][j];
			}
			else {
				dist[i][j] = INF;
			}
		}
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	int score = INF;
	int cnt = 0;
	vector<int> v;
	for (int i = 1; i <= n; i++) {	
		int max = 0;

		for (int j = 1; j <= n; j++) {
			if (max < dist[i][j] && dist[i][j] != 0) {
				max = dist[i][j];
			}
		}

		if (score > max) {
			score = max;
			cnt = 0;
			v.clear();
		}

		if (score == max) {
			cnt++;
			v.push_back(i);
		}
	}

	cout << score << ' ' << cnt << '\n';
	for (int i = 0; i < v.size(); i++)
		cout << v[i] << ' ';

	return 0;
}