[C++] 백준 1389번 - 케빈 베이컨의 6단계 법칙

기본적인 Floyd Warshall문제

사실 친구의 거리를 구하는것이 1이라서 BFS로도 풀 수 있는 문제인데 플로이드와샬을 좀 더 연습해보기 위해 플로이드와샬로 풀었다. 주의할 점은 거리(?)가 같을 때 작은 것의 번호를 출력해야한다는 것이다. 

#include <bits/stdc++.h>
#define endl '\n'
#define INF 987654321
using namespace std;

int n, m;
int arr[101][101];

int main() {

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

	cin >> n >> m;

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

	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		arr[a][b] = 1; arr[b][a] = 1;
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				int temp = arr[i][k] + arr[k][j];
				if (temp < arr[i][j]) arr[i][j] = temp;
			}
		}
	}
	vector<int> v;
	int ans = 9999999;
	int result = 0;
	for (int i = 1; i <= n; i++) {
		int temp = 0;
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			if (arr[i][j] == INF) continue;
			temp += arr[i][j];
		}
		if (ans > temp) {
			ans = temp;
			result = i;
		}
	}
	cout << result << endl;

	return 0;
}