플로이드 와샬1 [백준/C,C++] 1389번: 케빈 베이컨의 6단계 법칙 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를 실행한 뒤, 모든 노드를 방문했을 때의 깊이(depth)를 더한 값이 가장 작은 노드를 출력하면 됩니다. 모든 정점에서 모든 정점을 방문해야 할 때, 플로이드 와샬이라는 알고리즘을 사용할 수 있던데 자세한 내용은 ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4.. 2021. 4. 21. 이전 1 다음