케빈 베이컨의 6단계 법칙 (백준 1389)

안녕하세요. 오늘은 6단계를 설명할 거예요.

문제

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

아이디어

플로이드-워셜 알고리즘을 통해 최단 거리를 구하고 그 거리의 합이 가장 작은 사람을 출력하면 됩니다.

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int dp[111][111] = { 0 };

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N, M, i, j, k, a, b;
	cin >> N >> M;
	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
			if (i != j)
				dp[i][j] = 1e9;
	for (i = 0; i < M; i++)
	{
		cin >> a >> b;
		dp[a][b] = dp[b][a] = 1;
	}

	for (k = 1; k <= N; k++)
		for (i = 1; i <= N; i++)
			for (j = 1; j <= N; j++)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
	
	int mn = 2e9 , p;
	for (i = 1; i <= N; i++)
	{
		int sum = 0;
		for (j = 1; j <= N; j++)
			sum += dp[i][j];
		if (sum < mn)
		{
			mn = sum;
			p = i;
		}
	}
	cout << p;
}

감사합니다.