[백준] 1389 파이썬

문제

---

• 백준 1389 (실버1)

백준 1389

문제가 굉장히 길어서 바로 머리에 들어오지 않았지만 읽어보니 간단했다.
모든 사람들이 6단계 이내로 연결될 수 있다는 이야기를 들어본 적이 있는 것 같았다.
유저의 수가 최대 100명 관계의 수가 최대 5000명에 시간 제한이 2초여서 시간 제한은 널널한 편이였다.

내 코드

---

BFS를 활용하여서 코드를 작성하였다.
모든 관계에 대해서 몇 단계에 걸쳐있는지 구하고 이를 통해서 각 유저의 케빈 베이컨 수를 리스트에 저장했다.

import sys
from collections import deque
input = sys.stdin.readline

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

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

def bfs(start, end):
    visited = [0] * (n + 1)
    visited[start] = 1
    queue = deque([start])
    while queue:
        temp  = queue.popleft()
        if temp == end:
            return visited[temp]
        for x in graph[temp]:
            if not visited[x]:
                queue.append(x)
                visited[x] = visited[temp] + 1

for i in range(1, n):
    for j in range(i + 1, n + 1):
        step = bfs(i, j)
        kevin[i] += step
        kevin[j] += step

print(kevin.index(min(kevin)))