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

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

Solution

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(v):
    cnt =  [0] * (n+1)
    visited[v] = 1
    queue = deque()
    queue.append(v)

    while queue:
        x = queue.popleft()
        for i in graph[x]:
            if visited[i] == 0:
                visited[i] = 1
                cnt[i] = cnt[x] + 1
                queue.append(i)
    return sum(cnt)


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

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

배운점

이 문제는 배열로 1부터 n까지 돌며 방문체크를 위한 리스트를 반복해서 생성해 주고
방문하지 않았으면 bfs를 실행하여 result에 연결되는 단계들의 합을 넣어주는 방식으로 풀이 되었다.
처음 문제를 봤을땐 그냥 방문체크를 하며 돌면 되겠지 싶어서 visited를 한번만 생성하였는데
생각해 보니 방문체크는 각 번호 마다 필요하였고 각 번호마다 얼마나 걸리는지 도 합을 구해야 하기 때문에 BFS안에도 cnt라는 빈 리스트를 n+1만큼 생성하여 주었다.