백준 1325번: 효율적인 해킹

백준 1325번: 효율적인 해킹

from collections import deque
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
table = [[] for _ in range(N+1)]
for _ in range(M):
    A,B = map(int,input().split())
    table[B].append(A)
    #B 해킹 -> A 해킹

def bfs(x):
    queue = deque([x])
    visit=[0]*(N+1)
    visit[x] = 1
    cnt = 1
    while queue:
        t = queue.popleft()
        for i in table[t]:
            if not visit[i]:
                queue.append(i)
                visit[i] = 1
                cnt +=1
    return cnt

max_cnt = 0
res=[]
for i in range(1,N+1):
    result = bfs(i)
    if result > max_cnt:
        max_cnt = result
        res.clear()
        res.append(i)
    elif result == max_cnt:
        res.append(i)

print(*res)

문제 자체는 간단한 BFS 문제인데, N과 M의 범위가 크다. (0<N<=10,000, 0<M<=100,000) 그래도 시간 제한이 5초니까 널널하게 풀릴거라고 생각하고 그냥 BFS로 구현을 했는데... 시간 초과가 나왔다.
처음에는 결과를 배열에 저장해서 소팅한 다음에 출력하는 식으로 했어서 소팅이 문제였나, 하고 max_cnt를 계산해서 배열을 매번 새로 만들어주는 방법을 썼는데 그래도 시간 초과가 났다. 다른 사람들 코드를 찾아보니까 로직이 똑같은데도 계속 시간 초과가 났다.

from collections import deque
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
table = [[] for _ in range(N+1)]
hack = []
for _ in range(M):
    A,B = map(int,input().split())
    table[B].append(A)
    #B 해킹 -> A 해킹

def bfs(x):
    queue = deque([x])
    visit=[0]*(N+1)
    cnt = 1
    while queue:
        cnt+=1
        t = queue.popleft()
        visit[t] = 1
        for i in table[t]:
            if(visit[i]==0):
                queue.append(i)
    return cnt

max_cnt = 0
res=[]
for i in range(1,N+1):
    result = bfs(i)
    if result > max_cnt:
        max_cnt = result
        res.clear()
        res.append(i)
    elif result == max_cnt:
        res.append(i)

print(*res)

계속 시간 초과가 났던 코드다. 위에 있는 정답코드와 달라진 부분은 bfs 함수 부분인데, visit처리만 달라졌다. 사실 bfs 로직 자체에서는 visit를 어디서 처리해줘도 딱히 상관은 없는데... 생각해보면 queue에 넣을때 visit를 일단 처리를 해줘야 중복으로 값이 들어갈 가능성이 없어진다. 이걸 생각을 못해서 한참을 헤맸다;; (물론 문제에 따라서 또 어떻게 처리해줘야되는지가 다를 수도 있다) 숫자가 커질수록 이런 사소한 부분도 성능에 영향을 미치니까 (삐끗하면 시간초과나기때문..) 조심해야겠다...