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

문제 

케빈 베이컨의 법칙은 모든 사람들이 서로 아는 사람 6단계 이내로 거쳐서 연결될 수 있다는 법칙입니다. N명의 사람이 주어졌을 때 자신을 제외한 모든 사람 각각과 연결된 합을 구한 것을 케빈 베이컨의 합이라고 하는데 최소 합을 가지는 사람의 번호를 출력하면 됩니다.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1389)

풀이

간단하게 BFS를 통해 풀 수 있는 문제입니다. 무조건 6단계 이내로 연결되기 때문에 BFS 탐색을 위한 큐가 비었을 때는 다른 사람과 몇단계를 거쳐서 연결되었는지 알 수 있게 됩니다. BFS를 사람수만큼 반복해주면 각 사람마다 연결된 합을 구할 수 있습니다.

코드

https://github.com/kswim/Algorithm/blob/master/BFS/1389.cpp