플로이드-와샬

[백준] 1389. 케빈 베이컨의 6단계 법칙 - 파이썬

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 BFS로 단순하게 풀이하기에는, BFS의 기본 time complexity가 O(N+E) / O(N^2)이므로, 대충 생각해봐도 O(N^2(N+E)) => O(N^3+E*N^2) 정도, 또는 O(N^4) 정도의 time complexity가 된다. 그렇기에, O(N^3) 정도의 time complexity인 Floyd-Warshall(플로이드-..