[백준] 1389번 : 케빈 베이컨의 6단계 법칙 - Python(파이썬)

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

import sys
sys.setrecursionlimit(10**6)
from collections import deque

def bfs(a):
    check=[False]*(n+1)
    q=deque()
    q.append((a,0))
    check[a]=True
    sum=0

    while len(q)>0:
        v0,v1=q.popleft()
        sum+=v1
        for i in range(1,n+1):
            if arr[v0][i]==1 and check[i]==False:
                check[i]=True
                q.append((i,v1+1))
    return sum

n,m=map(int,input().split())
arr=[[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    arr[a][b]=arr[b][a]=1
count=1000
ans=0
for i in range(1,n+1):
    sum=bfs(i)
    if count>sum:
        count=sum
        ans=i
print(ans)