[백준][BFS] 1325. 효율적인 해킹

1325. 효율적인 해킹

1325번: 효율적인 해킹

 

• 내 풀이
  • for문 돌면서 1~n번 각각에서 시작하여 해킹할수 있는 만큼 cnt[n]에 +1 해가면서 저장
  • visited는 bfs(i)로 1-n번이 시작될때마다 초기화해줘야함

#a-> b 신뢰 : b 해킹하면 a 해킹가능
#가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터번호
from collections import deque

def bfs(i):
    queue.append(i)
    visited[i]=0
  
    while queue:
        x=queue.popleft()
        cnt[i]+=1
        for gh in graph[x]:
            if visited[gh]==-1:
                queue.append(gh)
                visited[gh]=0
                cnt[i]+=1
  

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

for i in range(m):
    a,b=map(int,input().split())
    graph[b].append(a)
  
queue=deque()
cnt=[0 for _ in range(n+1)]

for i in range(1,n+1):
    visited=[-1 for _ in range(n+1)]
    bfs(i)


result=[]
for idx, c in enumerate(cnt):
    if c==max(cnt):
        result.append(idx)

print(*result)