1389

[python3] 백준 1389 풀이 ( 케빈 베이컨의 6단계 법칙, 플로이드 워샬 )

이번 문제는 케빈 베이컨의 6단계 법칙이다. 케빈 베이컨이 할리우드의 핵 인싸라는 것을 인지하고 문제에 들어가자. 문제를 보자 문제가 상당히 길다. 읽어보면 그냥 네트워크 안에서 여러 사람들과 연결되어 있을때 모든 타인과 몇번만에 연결되어 있는지를 알아내어 최솟값을 가지는 즉, 허브 역할을 하는 사람을 구하면 된다. 문제를 잘 읽어보면 결국 N정점에서 N정점으로의 갈 때 얼마나 걸리는지를 구해야 한다. 그래야 한 노드에서 모든 노드에 방문할 때 케빈 베이컨의 수를 구할 수 있다. 즉, 모든 쌍 최단 거리 알고리즘을 사용하면 구할 수 있다. 모든 쌍 최단 거리 알고리즘의 대표적인 놈이 "플로이드 워샬"이다. 그러나! 플로이드 워샬은 O(N^3)이 걸리기 때문에 N값이 너무 크면 문제가 발생할 수 있다. 다..