[백준] 1325 효율적인 해킹

문제

• N개의 컴퓨터는 신뢰하는 관계와 신뢰하지 않는 관계로 이뤄져 있다.
• A가 B를 신뢰하는 경우, B를 해킹하면 A도 해킹할 수 있다.
• N개의 컴퓨터들 간의 신뢰하는 관계가 주어질 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호 출력하기\

 

• 1 <= N <= 10,000
• 1 <= 신뢰 관계 개수 <= 100,000

 

풀이 1

• DFS 또는 BFS로 연결된 컴퓨터의 개수를 모두 센다

pypy 로만 통과한다. -> 시간초과

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

def counting(graph, node) :
    q = deque([node])
    cnt = 0
    visited = [False] * (N+1)
    visited[node] = True

    while q :
        node = q.popleft()
        cnt += 1

        for nxt in graph[node] :
            if not visited[nxt] :
                q.append(nxt)
                visited[nxt] = True
    return cnt

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)

# 해킹 가능한 컴퓨터 수 계산하기
answer = [0] * (N+1)
for i in range(1, N+1) :
    answer[i] = counting(graph, i)

# 가장 많이 해킹 가능한 컴퓨터 번호 출력
maximum = max(answer)
for i in range(1, N+1) :
    if answer[i] == maximum :
        print(i, end=' ')

 

 

 

 

References

• 백준 그래프 탐색