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

문제 링크: https://www.acmicpc.net/problem/1389

 

플로이드 알고리즘을 쓰거나, 다익스트라 알고리즘을 n번 돌리면 됩니다

n<=100으로 작기 때문에 가능합니다.

플로이드 알고리즘을 돌린 다음 그래프를 찍어보면 이렇게 나옵니다. 각 행마다 저 값을 다 더하면 케빈 베이컨 수가 됩니다. 케빈 베이컨 수가 가장 작으면서 그 중 인덱스가 가장 작은 사람 출력하면 끝입니다.

#include <bits/stdc++.h>
using namespace std;

const int INF = 987654321;
int adj[100][100];

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

	int n, m;
	cin >> n >> m;

	while (m--) {
		int from, to;
		cin >> from >> to;
		--from, --to;
		adj[from][to] = 1;
		adj[to][from] = 1;
	}

	// floyd
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			if (i != j && !adj[i][j])
				adj[i][j] = INF;

	for (int k = 0; k < n; ++k)
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

	int min_bacon = 1e9;
	int min_index = -1;
	for (int i = 0; i < n; ++i) {
		int bacon = 0;
		for (int j = 0; j < n; ++j) {
			if (i == j) continue;
			bacon += adj[i][j];
		}

		if (min_bacon > bacon) {
			min_bacon = bacon;
			min_index = i;
		}
	}

	cout << min_index + 1 << '\n';
	

	return 0;
}