[백준] 1325번 효율적인 해킹 파이썬 코드

코드

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

n,m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
  x,y = map(int, input().split())
  graph[y].append(x) # 한 쪽만 연결 (A가 B를 신뢰하면 B 해킹 시 A도 해킹)

def bfs(i):
  queue = deque([i])
  visited = [False] * (n+1) # 함수 호출마다 방문 여부를 체크할 수 있어야 한다.
  visited[i] = True # list에 넣고 not in 시 시간 복잡도 증가, set이나 리스트의 강점인 인덱싱 사용하는 게 좋아보임
  count = 1
  while queue:
    popnum = queue.popleft()
    for k in graph[popnum]:
      if not visited[k]:
        queue.append(k)
        visited[k] = True
        count += 1
  return count
  
count_list = []
for i in range(1, n+1):
  count_list.append(bfs(i))
  
count_list_max = max(count_list)

for j in range(len(count_list)):
  if count_list[j] == count_list_max:
    print(j+1, end=' ')

시간초과 때문에 엄청 애먹었던 문제. 그마저도 pypy로 겨우 통과했다... bfs 코드 내에서 문제인지 아래 for문이 문제인지...( 그래도 최대 20만 아닌가...) 더 공부를 해야 보일 듯 싶다. 그리고 리스트에서 not in을 사용하기보다는 false, true를 이용해 체크하는 게 시간 효율이 좋다는 것도 확인했다. 당연한 말이겠지만, 이렇게까지 느낀 건 처음이다...