[BOJ] 1325 효율적인 해킹 파이썬

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

 

 

 

간선의 방향이 있는데, 글자를 잘못읽으면 완전히 다른 방향으로 간선을 설정해버릴 수 있으니 주의하자.

그것 빼고는 단순 bfs문제인데, 모든 정점에 대하여 bfs를 돌리는 경우를 생각했을때 파이썬으로 풀기에는 숫자가 너무 크다.

이것도 역시, 극한의 최적화를 이루어내지 않으면 파이썬이 아니라, pypy3로 풀어야 하는 문제이다.

 

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

n, m = map(int, input().rstrip().split(" "))
graph = [[] for _ in range(n+1)]

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


def bfs(x):
    global graph, n

    q = deque()
    q.append(x)
    visited = [0] * (n+1)
    visited[x] = 1
    count = 0

    while(len(q) != 0):
        start = q.popleft()
        count += 1
        for dest in graph[start]:
            if(visited[dest] == 0):
                q.append(dest)
                visited[dest] = 1

    return count


maximum = -1
maximum_idx = []
for i in range(1, n+1):
    if(len(graph[i]) > 0):
        tmp = bfs(i)
        if(tmp > maximum):
            maximum = tmp
            maximum_idx = [i]
        elif(tmp == maximum):
            maximum_idx.append(i)

print(*maximum_idx)

 

추가로 이 문제를 통해서, *로 unpack하여 출력할때 " "공백으로 join한것과 같은 효과를 얻을 수 있다는 것을 깨달았다.