백준 1325 효율적인 해킹

과정

• BFS
• 모든 컴퓨터에 대해서 bfs로 해킹할 수 있는 모든 컴퓨터 수를 구하기.
• 구한 수는 배열에 저장했다.

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

N, M = map(int, input().split())

lst = [[] for _ in range(N+1)]
ans_lst = [0] * (N+1)

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

def bfs(x1):
    queue = deque([x1])
    visited = [False] * (N+1)
    visited[x1] = True
    cnt = 0
    while queue:
        x = queue.popleft()
        cnt += 1
        visited[x] = True
        for i in lst[x]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
    ans_lst[x1] = cnt

for i in range(1, N+1):
    bfs(i)

max_num = max(ans_lst)
for i in range(1, N+1):
    if ans_lst[i] == max_num:
        print(i, end=" ")

• 일반적인 bfs 문제였지만, 시간초과를 해결하기가 쉽지 않았다. 좀 오래걸리는 문제.
• Pypy로는 정답이 뜨지만, Python 으로는 시간초과가 난다는 듯 하다.