BOJ 1325번 - 효율적인 해킹

[백준 온라인 저지 링크]

1325번: 효율적인 해킹

우선 이 문제는 테스트케이스 범위로 인해 DFS로 풀면 시간 초과가 납니다.

(※ 시간이 아니더라도, 파이썬의 최대 재귀 제한에 걸릴 예정입니다.)

맞아 봐서 알아요! 😌

[정답 코드 - Python]

from collections import deque

N, M = map(int, input().split())
trust = [[] for _ in range(N + 1)]
count = [0] * (N + 1)


def BFS(node):
    q = deque()
    q.append(node)
    infected = [False] * (N + 1)
    infected[node] = True
    while q:
        node = q.popleft()
        for nextNode in trust[node]:
            if infected[nextNode] == True:
                continue
            else:
                q.append(nextNode)
                infected[nextNode] = True

    return infected.count(True)


for i in range(M):
    dist, src = map(int, input().split())
    trust[src].append(dist)

for node in range(1, N + 1):
    count[node] = BFS(node)

for i in range(len(count)):
    if count[i] == max(count):
        print(i, end=" ")