Boj 1389) 케빈베이컨의 6단계 법칙

문제

백준 1389

설명

가중치가 없어서 BFS 가 더 빠른 방법임(O(v*e)).

하지만 요구사항이 가중치가 있다면 Floyd-Warshall 방법을 써야함.

시간 복잡도

O(v^3)

코드

int dp[101][101];

int main()
{
	fastio;

	int n, m, t1, t2;
	cin >> n >> m;
	
	// Self : 0, No Weighted Link : 1, No Link : INF
	fill(dp[0], dp[100] + 101, 1000000);
	for (int i = 1; i <= n; i++)
		dp[i][i] = 0;
	for (int i = 0; i < m; i++)
	{
		cin >> t1 >> t2;
		dp[t1][t2] = 1;
		dp[t2][t1] = 1;
	}
	
	// Floyd-Warshall
	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			{
				if (dp[i][k] + dp[k][j] < dp[i][j])
					dp[i][j] = dp[i][k] + dp[k][j];
			}
	
	// Calc Answer
	int ans = 0, ans_v = 10000000;
	for (int i = 1; i <= n; i++)
	{
		t1 = 0;
		for (int j = 1; j <= n; j++)
			t1 += dp[i][j];
		if (ans_v > t1)
		{
			ans_v = t1;
			ans = i;
		}
	}
	
	cout << ans;
}