[BOJ][python] 1325. 효율적인 해킹

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

1325번: 효율적인 해킹

---

💡IDEA

BFS를 사용하는 문제이다.

현재 컴퓨터를 신뢰하는 컴퓨터를 찾아서 BFS를 돌며 연결된 컴퓨터 개수를 카운트해주면 된다.

개수를 저장해뒀다가 가장 큰 값을 가진 인덱스를 순서대로 출력한다.

처음에 deque에 cnt까지 넣어서 BFS를 돌리는 실수를 했다. 그냥 다짜고짜 개수 세면 된다.

시간이 꽤 오래 걸려서 시간초과일 줄 알았는데 다행히 통과했다.

 

📌CODE

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

def bfs(n):
    q = deque([n])
    v = [0]*(N+1)
    v[n] = 1
    cnt = 1
    while q:
        cn = q.popleft()
        for nn in coms[cn]:
            if not v[nn]:
                q.append(nn)
                v[nn] = 1
                cnt += 1
    return cnt

N, M = map(int, input().split())
coms = [[] for _ in range(N+1)]

for _ in range(M):
    A, B = map(int, input().split())
    coms[B].append(A)

res = [0]
for i in range(1, N+1):
    res.append(bfs(i))
max_res = max(res)

for i in range(1, N+1):
    if res[i]==max_res:
        print(i, end=' ')