[BOJ] 효율적인 해킹

---

코드

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

def bfs(v):
    visited = [0]*(n+1)
    ret = 0
    q = deque([v])
    visited[v] = 1
    while q:
        cur = q.popleft()
        ret += 1
        for adj in graph[cur]:
            if not visited[adj]:
                visited[adj] = 1
                q.append(adj)
                
    return ret
                
        
# input 
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[b].append(a)

# bfs
ans = []
max_num = 0

for i in range(1, n+1):
    ret = bfs(i)
    if ret > max_num:
        ans.clear()
        ans.append(i)
        max_num = ret
    elif ret == max_num:
        ans.append(i)

ans.sort()
print(' '.join(map(str,ans)))

결과

풀이 방법

• 전형적인 단방향 그래프 bfs 문제였다.
• 신뢰관계를 이차원 리스트로 저장하고 각 컴퓨터를 시작노드로 하여 bfs를 수행하면 된다.

---