풀이 보관함
[C++] 백준 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;
}