2022.03.17 [백준] (python 파이썬) 케빈 베이컨의 6단계 법칙

 

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

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

---

풀이

이 문제는 그래프를 이용해 각 번호에서 갈 수 있는 번호를 저장했다.

이 후, 각 번호에서의 케빈 베이컨의 수가 최저인지 확인 하기 위해 min과 최저이면 어떤 번호에서 최저인지 확인하기 위해 min_p를 선언했다.

그리고 for문을 돌려 각 번호에서의 케빈 베이컨 수를 bfs를 이용해서 구했다. 그리고 이전의 케빈 베이컨 수와 비교하여 작으면 min과 min_p를 업데이트해주었다.

 

from collections import deque
 
n,m=map(int, input().split())
graph=[[] for i in range(n+1)]
 
for i in range(m):
    x,y=map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
 
min=10**6
min_p=0
 
for i in range(1,n+1):
    vis = [-1] * (n + 1)
    deq = deque()
    deq.append(i)
    vis[i]=0
    while deq:
        x=deq.popleft()
        for j in graph[x]:
            if vis[j]==-1:
                vis[j]=vis[x]+1
                deq.append(j)
    if sum(vis)<min:
        min=sum(vis)
        min_p=i
print(min_p)