[ BOJ 1325 ] 효율적인 해킹(Python)

문제

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

A가 B를 신뢰할 때, B를 해킹하면 A도 해킹할 수 있다.
신뢰하는 관계가 주어졌을 때, 가장 많이 해킹할 수 있는 컴퓨터의 수를 구하는 문제이다.

문제 풀이

1. 신뢰하는 관계가 [a ➣ b] 다음과 같이 주어지므로,그래프 연결은 graph[b].append(a) 로 해준다.
2. 연결된 컴퓨터가 있을 경우에만 bfs 함수의 매개변수로 넣어준다.
   2-1. 연결된 컴퓨터를 방문 안했을 때만 queue에 넣어준다.
   2-2. 컴퓨터의 수를 1 증가시켜준다.
3. 반환된 컴퓨터의 수를 비교해서 더 큰 값을 리스트로 저장해준다.
   만약에 반환된 컴퓨터의 수가 같으면 값을 리스트에 추가해준다.

코드

python3으로 제출하면 시간초과가 발생하지만 pypy로 제출하니 잘 제출된다.

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

def bfs(v):
    queue = deque()
    queue.append(v)
    visited = [False] * (n+1)
    visited[v] = True
    cnt = 1

    while queue:
        target = queue.popleft()

        for new_target in graph[target]:
            if not visited[new_target]:
                queue.append(new_target)
                visited[new_target] = True
                cnt += 1
    return cnt

#n개의 컴퓨터, m개의 관계
n,m = map(int,input().rstrip().rsplit())
graph = [[] for _ in range(n+1)]
compare,answer, answer_list = 0, 0, []

queue = deque()

visited = [False] * (n+1)

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

for i in range(1,len(graph)):
    if len(graph[i]) > 0:
        compare = bfs(i)
        if answer < compare:
            answer = compare
            answer_list = [i]
        elif answer == compare:
            answer_list.append(i)

for ans in answer_list:
    print(ans,end=" ")
print()