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

🔗 문제

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

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

 

✍️ 풀이

 

무방향 그래프에서 모든 정점의 최단 경로를 구해야 한다?

 

 

플로이드 와샬 문제였다.

 

 

주의 사항

• 무방향 그래프이므로 a→b면 b→a임을 잊지 말자.
• 플로이드 와샬이 방문하지 않은 인접행렬의 초기값은 INF이지만 이 문제에서 자기 자신으로 가는 값은 0으로 설정하는 것에 유의해야 한다.
• 출발노드가 중간노드나 목적지가 되는건 찾을 필요가 없다. 

 

💾  소스

#include <iostream>
#include <vector>
#include <cmath>

const int INF = 1e9;
std::vector<std::vector<int>> adj;
int V, E, min = INF;

void input()
{
	int a, b;

	std::cin >> V >> E;

	adj.resize(V + 1, std::vector<int>(V + 1, INF));
	
	for (int i = 1; i <= V; ++i)
		adj[i][i] = 0;

	while (E--)
	{
		std::cin >> a >> b;
		adj[a][b] = adj[b][a] = 1;
	}
}

int main()
{
 
	int answer = 0;

	input();
	
	std::vector<int> kb(V + 1, 0);

	for (int k = 1; k <= V; ++k)
	{
		for (int i = 1; i <= V; ++i)
		{
			for (int j = 1; j <= V; ++j)
			{
				if (i == j || i == k || j == k) continue;

				adj[i][j] = std::min(adj[i][j], adj[i][k] + adj[k][j]);
			}
		}
	}

	for (int i = 1; i <= V; ++i)
	{
		for (int j = 1; j <= V; ++j)
		{
			kb[i] += adj[i][j];
		}

		if (min > kb[i])
		{
			min = kb[i];
			answer = i;
		}
	}

	std::cout << answer;

	return 0;

}