[실버1] 1325번 : 효율적인 해킹

🛠 문제

https://www.acmicpc.net/problem/1325

👩🏻‍💻 해결 방법

dfs를 사용하려 했으나 시간초과 때문에 bfs를 사용하여 해결해야 했다
maxcnt를 이용해 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호들을 출력할 수 있다

소스 코드

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

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]

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

maxcnt = 0
answer = []

for i in range(1, n+1):
  visit = [0] * (n+1)
  visit[i] = 1
  q = deque([i])

  cnt = 0
  while q:
    v = q.popleft()
    for node in graph[v]:
      if visit[node] == 0:
        visit[node] = 1
        cnt += 1
        q.append(node)
  
  if maxcnt < cnt:
    maxcnt = cnt
    answer = [i]
  elif maxcnt == cnt:
    answer.append(i)

print(*answer)