백준 / BOJ / 1389 케빈 베이컨의 6단계 법칙 C++

www.acmicpc.net/problem/1389

1389번: 케빈 베이컨의 6단계 법칙

케빈 베이컨의 6단계 법칙이라는 유명한 법칙이다. 세상 모든 사람은 6단계 안으로 만날 수 있다는 것이다. 

 

문제는 간단하다. 사람들이 숫자로 주어지고, 사람들의 관계가 주어졌을 때 케빈 베이컨 수가 가장 적은 사람을 고르는 문제이다. 케빈 베이컨 수는 사람들 사이의 최소 링크 수의 합이다.

 

예를 들어, 사람들 사이의 관계가 (1,3), (1,4), (4,5), (4,3), (3,2) 로 주어지면, 1은 2와 1->3->2 2개의 링크를 건너면 되고, 3과는 1->3 으로 1개의 링크, 4와도 1->4 1개의 링크, 5와는 1->4->5 2개의 링크를 최소로 건널 수 있다. 

이 수의 합 2+1+1+2 = 6 이 1의 케빈베이컨 수이다. 

 

bfs 를 이용하여 계산하였다. bfs의 복잡도는 인접리스트, 인접행렬 등으로 계산했을 때 복잡도가 조금 다르지만, 두 경우 모두 모든 사람이 다 연결되어있다고 생각하면 둘 다 O(n^2) 이다. (인접행령 : O(v^2), 인접리스트 : O(v+e), v: 정점 개수, e: 간선 개수)

 

start 사람이 end 사람을 만날 때까지 최소 경로를 bfs 를 이용하여 구현하였다. 총 탐색 회수는 n^2번, 각 탐색마다 O(n^2)의 bfs를 이용하므로 총 복잡도는 O(n^4)이다. n=100이 최대값이고, 제한 시간이 2초가 주어져있으므로 넉넉하게 풀 수 있다. (start와 end 번호를 서로 바꾸어도 최소 경로는 같은 걸 이용하면 좀 더 최적화를 할 수 있지만, 돌려봤을 때 0ms가 나와 굳이 하지 않았다.)

 

코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;

int n, m;
vector<int>user[101];
bool check[101];
pair<int, int>result = { 987654321,987654321 }; // user, sum of dist

void make_user()
{
	cin >> n >> m;
	while (m--)
	{
		int a, b;
		cin >> a >> b;
		user[a].push_back(b);
		user[b].push_back(a);
	}
}

int bfs(int start, int end)
{
	memset(check, false, sizeof(check));
	check[start] = true;

	int Dist = 0;
	int res = 0;

	queue<pair<int, int>>q;
	q.push({ start,Dist });

	while (!q.empty())
	{
		int now = q.front().first;
		int dist = q.front().second;
		q.pop();

		if (now == end)
		{
			res = dist;
			break;
		}

		for (int i = 0; i < user[now].size(); i++)
		{
			if (!check[user[now][i]])
			{
				check[user[now][i]] = true;
				q.push({ user[now][i],dist + 1 });
			}
		}
	}

	return res;
}

int main()
{
	make_user();

	int sum;
	for (int i = 1; i <= n; i++)
	{
		sum = 0;
		for (int j = 1; j <= n; j++)
		{
			if (i == j)
				continue;

			sum += bfs(i, j);
		}
		if (result.second > sum)
		{
			result = { i,sum };
		}
		if (result.second == sum)
		{
			if (result.first > i)
				result = { i,sum };
		}
	}

	cout << result.first;
}