[백준] #1389 케빈 베이컨의 6단계 법칙 (python)

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

문제 설계

모든 노드에 대해서 bfs를 한다.

 

문제 풀이

from collections import deque

n,m=map(int,input().split())

graph=[[] for _ in range(n+1)]

for _ in range(m):
    x,y=map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

min=999999999

def bfs(start):
    visited=[-1]*(n+1)
    q=deque()
    q.append(start)
    cnt=0
    visited[start]=0

    while q:
        now=q.popleft()

        for next in graph[now]:
            if visited[next]==-1:
                visited[next]=visited[now]+1
                cnt+=visited[next]
                q.append(next)
    return cnt


for i in range(1,n+1):
    cnt=bfs(i)
    if cnt < min:
        min=cnt
        answer = i
print(answer)

i를 1부터 시작하기 때문에 여러 명일 경우에도 작은 번호가 출력된다.