[BOJ/Python] 백준 1325번 - 효율적인 해킹

백준 #1325 효율적인 해킹

1325번: 효율적인 해킹

 

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

def bfs(s):
    visited = [False] * (n+1)
    q = deque([s])
    visited[s] = True
    cnt = 1
    while q:
        w = q.popleft()
        for v in graph[w]:
            if visited[v]: continue
            visited[v] = True
            q.append(v)
            cnt += 1
    return cnt


n, m = map(int, input().split())  # n: 컴퓨터 개수, m: 신뢰 관계 개수
graph = [[] for _ in range(n+1)]

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


maxCnt = 0
maxCom = []
for i in range(1, n+1):
    cnt = bfs(i)
    if maxCnt < cnt:
        maxCnt = cnt
        maxCom = [i]
    elif maxCnt == cnt:
        maxCom.append(i)

print(*maxCom)

신뢰하는 관계를 방향 그래프로 나타내 그래프 탐색을 통해 풀었다. 각 노드에서 갈 수 있는 모든 노드의 개수가 곧 해당 컴퓨터를 해킹했을 때 해킹할 수 있는 컴퓨터의 개수가 된다.

python으로 제출했을 때 타임 아웃이 돼서 pypy로 제출했다. 시작하는 노드를 모든 번호로 하지 않고 신뢰하는 관계를 가진 컴퓨터만 하면 개선할 수 있을 것 같다. 

5 4
3 1
3 2
4 3
5 3

이렇게 입력이 들어왔을 때 1, 2, 3 만 확인한다는 의미!