실버 쯤이야 - 그래프의 재미 (1389번 케빈 베이컨)

#1389번 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389

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

 

확실히 문제가 안풀리는 날에는 문제 이해를 제대로 안한 경우가 많아서 속상하다.

 

신중에 신중을 기하는 내가 되길 바란다.

 

내 코드

from collections import deque
N, M = map(int, input().split())
network = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    network[a].append(b)
    network[b].append(a)

answer = [0, N**2]  # person_number, cnt
# bfs
for p in range(1, N+1):  # 하나씩 bfs를 다 돌려야하나? 아니면 한번만 돌려서 할 수 있을까?
    que = deque()
    que.append([p, 0])
    visited = [False]*(N+1)
    visited[p] = True
    while que:
        x, cnt = que.popleft()
        for np in network[x]:
            if not visited[np]:
                visited[np] = cnt + 1
                que.append([np, cnt+1])
    visited[p] = 0
    result = sum(visited)
    answer = [p, result] if result < answer[1] else answer

print(answer[0])

BFS를 통해 구현했다. 모든 노드에서 출발하는 bfs를 전부 구현했기 때문에 시간초과가 나지 않을까 걱정됐지만 부드럽게 통과해서 기뻤다.

 

다른 사람의 코드도 비슷비슷해서 더 작성할 내용은 없다.

 

그동안의 풀이에서는 가볍게 풀린 문제는 기록하지 않았다.

 

하지만 이제 모두 기록하고자 한다. 기록한 문제가 더 기억에 남는 듯 하기 때문에...

 

화이팅이다.