(Python) - BOJ(1389번) : 케빈 베이컨의 6단계 법칙

https://www.acmicpc.net/problem/1389

1389번: 케빈 베이컨의 6단계 법칙

---

• 해설 : 

케빈 베이컨의 6단계 법칙에 의하면 전 세계의 모든 사람은 지인을 6번만 거치면 모두 아는 사람이라고 한다.

N명의 사람과, 연결관계가 주어질 때 각 사람들이 나머지 사람들에 총 몇 단계를 거쳐야 아는 사이가 되는지 구하고 

거쳐야하는 단계들의 합 중에 최솟값을 가진 사람을 찾는 문제이다.

 

 

 

---

• 풀이 :

사람들간의 연결관계가 주어졌으므로 모든 사람에 대해 각 사람을 bfs로 탐색하고 모든 거리들의 합을 리턴하도록 하였다. 

거리들의 합 중 min값을 가진 인덱스를 출력하도록 구현하였다.

 

그래프에서 모든 사람들에 대해 모든 노드 탐색하는 거리를 찾는 방법이므로 플로이드-와샬 알고리즘을 사용해도 해결할 수 있다.  

 

 

 

---

• 소스코드 : 

 

import sys
from collections import deque
def bfs(start):
    cnt = 0
    w = [0 for _ in range(n+1)]
    queue = deque([start])
    while queue:
        p = queue.popleft()
        for k in relations[p]:
            if w[k] == 0 and k != start:
                queue.append(k)
                w[k] = w[p]+1
    answer[start-1] = sum(w)
 
if __name__ == "__main__":
    n,m = map(int,sys.stdin.readline().split())
 
    relations = [[] for _ in range(n+1)]
    for _ in range(m):
        A,B = map(int,sys.stdin.readline().split())
        relations[A].append(B)
        relations[B].append(A)
    answer = [0 for _ in range(n)]
    for i in range(1,n+1):
        bfs(i)
    print(answer.index(min(answer))+1)