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

문제

BOJ 링크

---

풀이

플로이드-워셜 문제다.

3중 반복문을 활용해 모든 노드의 최단 경로를 구한 후, kb 배열을 만들어 각 노드의 케빈-베이컨 수를 저장했다.

모든 노드의 가중치를 kb에 더하면 자기 자신도 함께 계산되므로 반복문 후열에 fw[i][i] 노드만큼 빼준다.

코드

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

int fw[101][101];
int kb[101] = { 0, };

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

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			kb[i] += fw[i][j];
		}
		kb[i] -= fw[i][i];
	}

	int ans, min = 1e9;
	for (int i = 1; i <= n; i++)
	{
		if (kb[i] < min)
		{
			min = kb[i];
			ans = i;
		}
	}

	return ans;
}

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

	// input & init
	int n, m;
	cin >> n >> m;

	fill(&fw[0][0], &fw[n][n+1], 1e9);

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

	// solve
	cout << floydWarshall(n);

	return 0;
}

결과