[백준] 1389번 케빈 베이컨의 6단계 법칙 (파이썬)

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):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def bfs(graph, v):
    queue = deque([v])
    visited[v] = True
    tmp = [0]*(n+1)
    
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                tmp[i] = tmp[v] + 1
    
    return sum(tmp)

result = []
for i in range(1, n+1):
    visited = [False]*(n+1)
    result.append(bfs(graph, i))
m = min(result)
print(result.index(m)+1)

플로이드워셜

n, m = map(int, input().split())
INF = float('inf')
graph = [[INF]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    for j in range(n+1):
        if i == j:
            graph[i][j] = 0
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1
    
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

result = []
for i in range(1, n+1):
    tmp = sum(graph[i][1:])
    result.append(tmp)
m = min(result)
print(result.index(m)+1)