[백준/BOJ] 백준 1389번 : 케빈 베이컨의 6단계 법칙

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

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

플로이드 알고리즘을 통해 각 정점들 사이의 최단 경로를 계산하고, 케빈 베이컨의 수가 가장 작은 사람을 찾았다.

 

코드

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

int n, m;
int adj[101][101];

int Solve()
{
	int ret;
	int min_num = 987654321;

	//플로이드 알고리즘을 이용해 각 정점까지 가는 최단 경로를 찾는다
	for (int i = 1; i <= n; i++)
		adj[i][i] = 0;

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

	//케빈 베이컨의 수가 가장 작은 사람을 찾는다
	for (int i = 1; i <= n; i++)
	{
		int num = 0;

		//i의 케빈 베이컨의 수를 구한다
		for (int j = 1; j <= n; j++)
		{
			num += adj[i][j];
		}

		//지금까지 구한 케빈 베이컨의 최소 값보다 i사람의 케빈 베이컨의 수가 더 작을때
		if (min_num > num)
		{
			min_num = num; //케빈 베이컨의 최소값을 갱신한다
			ret = i; //i를 케빈 베이컨의 수가 가장 작은 사람으로 갱신한다
		}
	}

	return ret;
}

//처음 그래프를 초기화 할때 모든 노드가 연결되어 있지 않다는 의미로 매우 큰 수를 넣는다
void preAdj()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			adj[i][j] = 987654321;
}

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

	int u, v;

	cin >> n >> m;

	preAdj();

	for (int i = 0; i < m; i++)
	{
		cin >> u >> v;
		adj[u][v] = 1;
		adj[v][u] = 1;
	}

	cout << Solve();
	
	return 0;
}