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

-문제: https://www.acmicpc.net/problem/1389

쉬운 문제인데 못 풀었다

너무 복잡하게 생각해서 그런것 같은데 기본 bfs를 이용하면 쉽게 풀린다 

 

-정답풀이: 

10번,18번,21번을 생각하지 못해서 틀린 문제다

from collections import deque

n,m= map(int,input().split())
graph=[[] for _ in range(n+1)]

for _ in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def bfs(v):
    num=[0]*(n+1)
    queue=deque()
    queue.append(v)
    visit[v]=1
    while queue:
        x=queue.popleft()
        for i in graph[x]:
            if not visit[i]:
                num[i]=num[x]+1
                queue.append(i)
                visit[i]=1
    return sum(num)
            

ans=[]
for i in range(1,n+1):
    visit=[0]*(n+1)
    ans.append(bfs(i)) #케빈 값들 넣는다
    
k=min(ans)
print((ans.index(k))+1)