(Python) - BOJ(1325번) : 효율적인 해킹

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

1325번: 효율적인 해킹

---

• 문제 : 

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

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

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

 

 

 

---

• 풀이 :

주어진 N의 범위가 10,000이고 M의 범위가 100,000이므로 시간초과에 간당간당하게 안걸렸다.

A,B가 주어질 때, B -> A 쪽으로 그래프의 간선을 연결하고 1부터 N까지 모든 노드에 대해 갈 수 있는 노드의 개수를 카운팅한다.  이 값이 max일 경우에만 시작노드를 정답배열에 넣어 마지막에 출력하면 된다. 

 

 

 

---

• 소스코드 : 

import sys
from collections import deque
def bfs(start):
    queue = deque()
    queue.append(start)
    check = [0]*(N+1)
    check[start] = 1
    while queue:
        X = queue.popleft()
        for Y in trust[X]:
            if check[Y] == 0:
                check[Y] = 1
                queue.append(Y)
    return sum(check)


if __name__ == "__main__":
    N,M = map(int,sys.stdin.readline().split())
    trust = [[] for _ in range(N+1)]
    answer = []
    m = 0
    for _ in range(M):
        x,y = map(int,sys.stdin.readline().split())
        trust[y].append(x)
    for start in range(1,N+1):
        x = bfs(start)
        if m < x:
            answer = [start]
            m = x
        elif m == x:
            answer.append(start)
    print(' '.join(map(str,answer)))