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

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

---

아이디어

1. 친구관계를 입력받으면 friends 리스트에 양방향으로 넣어준다.
   ex) 2 4일 때, friends[2] = [4], friends[4] = 2
2. BFS 함수에 1부터 n까지 모두 넣으면서 케빈 베이컨의 수가 가장 작은 번호를 출력한다.
   => BFS 함수
   2-1) 파라미터 k를 초기 queue에 넣는다.
   2-2) queue에서 먼저 들어온 원소(a)를 pop하고
   friends[a]의 원소들을 모두 훑으면서 몇 단계인지 기록 후, queue에 넣는다. (반복)
   +) 몇 단계인지 기록
   : i가 j의 몇 단계로 연결된 친구인지 graph[i][j]에 기록한다.

---

코드

from collections import deque
def BFS(k):
    queue = deque([])
    queue.append(k)
    while queue:
        a = queue.popleft()
        for num in friends[a]:
            if num == k: continue
            if graph[k][num] == 0:
                graph[k][num] = graph[k][a]+1
                queue.append(num)
    return sum(graph[k])

n, m = map(int, input().split())
graph = [[0]*(n+1) for _ in range(n+1)] # 몇 단계인지 기록할 리스트
friends = [[] for _ in range(n+1)] # 누가 누구의 친구인지 기록할 리스트
for _ in range(m): # 양방향 만들기
    a, b = map(int, input().split())
    friends[a].append(b)
    friends[b].append(a)

temp = 500000
answer = 0
for i in range(1, n+1):
    if temp > BFS(i):
        temp = BFS(i)
        answer = i
print(answer)