[알고리즘] 효율적인 해킹 백준 1325 python

문제 바로가기

풀이

bfs문제입니다.
A가 B를 신뢰하면, B를 해킹하면 A 또한 해킹할 수 있는 단방향으로 이루어져있습니다.
list[i]에 i를 신뢰하는 컴퓨터의 목록을 저장하고, bfs 알고리즘을 사용하면 되는 문제입니다.
bfs 내에서 큐에 시작 노드를 넣고 list[start] 즉, start가 해킹할 수 있는 컴퓨터들을 찾아내고,
그 컴퓨터들 중에 방문하지 않은 컴퓨터들은 큐에 추가하고 방문처리를 하고, cnt를 하나 올려주면 됩니다.

import sys
import collections

def bfs(start):
  cnt = 1

  queue = collections.deque()
  queue.append(start)

  visited = [0 for _ in range(n+1)] 
  visited[start] = 1
  
  while queue:
    u = queue.popleft()
    for i in list[u]:
      if not visited[i]:
        queue.append(i)
        visited[i] = 1
        cnt +=1
        
  return cnt


n, m = map(int, sys.stdin.readline().split())
#딕셔너리
list = [[] for i in range(n+1)]

for _ in range(m):
  a, b = map(int, sys.stdin.readline().split())
  list[b].append(a)

result = []
max_cnt = 0

for i in range(1, n+1):
  cnt = bfs(i)
  if max_cnt == cnt:
    result.append(i)
  if cnt > max_cnt:
    max_cnt = cnt
    result = []
    result.append(i)


print(*result)