백준 1389번 파이썬 문제풀이(케빈 베이컨의 6단계 법칙)

---

간단히 각 점에서 부터 bfs돌면서 각각 노드마다 거리를 계산해서 계속 더해주면 된다. 단, 이문제는 dfs로는 풀 수 없고 bfs로 풀어야하는 문제라는 것만 유의하면 된다. 또한 한가지 더 유의할 점이 관계가 중복돼서 제공될 수 있기 때문에 관계를 저장할 때 리스트가 아닌 셋으로 저장했다.

 

from collections import deque

N, M = map(int, input().split())
graph = [set() for _ in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)

bacon = []  # 베이컨 수 저장


def bfs(v):
    global result
    visited[v] = True
    queue = deque([[v, 0]])

    while queue:

        start, count = queue.popleft()
        result += count
        for i in graph[start]:
            if not visited[i]:
                visited[i] = True
                queue.append([i, count + 1])


for i in range(1, N + 1):
    visited = [False] * (N + 1)
    result = 0
    bfs(i)
    bacon.append(result)

print(bacon.index(min(bacon)) + 1)