[백준] 1325번 - 효율적인 해킹 (파이썬)

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

# 효율적인 해킹
import sys
from collections import deque
input = sys.stdin.readline


def count(where):
    q = deque()
    q.append(where)
    visited = [False] * (N+1)
    visited[where] = True
    cnt = 1
    while q:
        node = q.popleft()
        for nnode in arr[node]:
            if not visited[nnode]:
                q.append(nnode)
                cnt += 1
                visited[nnode] = True
    return cnt


N, M = map(int, input().split())
arr = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    arr[b].append(a)

result = []
for i in range(N+1):
    result.append(count(i))

max_value = max(result)
for i in range(1, N+1):
    if result[i] == max_value:
        print(i, end=' ')

 

BFS

1. 신뢰하는 컴퓨터 인접 리스트 정의

2. 전체 컴퓨터를 각각 BFS처리 (q가 빌 때 까지)

  - 신뢰받는 컴퓨터가 있으면, cnt += 1 하고 q에 append

  - cnt리턴하여 result 배열에 append

3. 배열에서 최댓값을 구하고 해당 값을 가진 인덱스 반환(컴퓨터는 1번부터 시작 주의)