[백준] 1325번 효율적인 해킹(python)

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

1325번: 효율적인 해킹

 

1. 난이도 실버1

 

2. 내가 작성한 코드

from collections import deque
import sys

input = sys.stdin.readline

n, m = map(int, input().rstrip().split()) #n=컴퓨터개수 m=신뢰관계

maps = [[] for _ in range(n+1)]
answer = []

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

def bfs(cnt, x):

    queue = deque()
    queue.append(x)
    visit[x] = 0

    while queue:
        popX = queue.popleft()

        for i in maps[popX]:
            if visit[i] == -1:
                cnt+=1
                visit[i] = 0
                queue.append(i)

    return cnt

for i in range(1,n+1):
    visit = [-1] * (n + 1)
    cnt = 0
    answer.append(bfs(cnt, i))

max_num = max(answer)

for i in range(n):
    if answer[i] == max_num:
        print(i+1,end=" ")

 

각 정점을 start로 두고 bfs를 돌려줘야 하기 때문에 매 번 visit를 초기화한다.

 

(B를 해킹할 경우 A를 해킹할 수 있으니 maps[b].append(a)로 인접리스트 만들어줘야 함!!!!)