백준 1325번. 효율적인 해킹 (Python / 파이썬)

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.
이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.
이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력

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

출력

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

---

문제 풀이

먼저, 컴퓨터간의 신뢰 관계를 그래프로 나타냈습니다.

컴퓨터 A가 B를 신뢰하면 B가 해킹당하면 A도 해킹을 당하게 됩니다.

따라서 그래프를 연결할 때 B에서 A 방향으로 연결해주었습니다.

 

이처럼 그래프로 관계를 표현한 뒤 특정 컴퓨터가 해킹 당했을 때

같이 해킹 당하는 컴퓨터의 개수를 세기 위해 탐색을 해주어야 합니다.

따라서 BFS 알고리즘을 이용했습니다.

 

먼저 각 노드에서 탐색을 수행해줍니다.

이때 방문했음을 체크할 배열은 매번 초기화 해주어야 합니다.

BFS 알고리즘을 수행하며 큐에 노드가 새로 삽입될 때마다 count를

세어주었습니다. 왜냐하면 노드가 탐색할 수 있는 노드들은 모두

해킹 가능하다는 뜻이기 때문입니다.

 

이렇게 구한 count중 최대 count 값을 구해주고 

각 노드 번호와 그에 해당하는 count 값을 새로운 list에 저장해줍니다.

만약 list에 저장된 count 값이 최대 count 값과 같다면 

노드 번호를 출력하도록 해주었습니다.

 

완성한 코드를 Python3로 제출하면 시간초과 판정이 납니다.

따라서 저는 PyPy3로 제출했습니다.

---

My Code

from collections import deque

def bfs(start):
    count = 0
    q = deque()
    q.append(start)
    visited[start] = 1
    while q:
        now = q.popleft()    # 큐에서 꺼냄
        for i in graph[now]: # 연결된 노드 확인
            if visited[i] == 0: # 방문하지 않았다면
                visited[i] = 1  # 방문처리
                q.append(i)     # 큐에 삽입
                count += 1      # 개수 세어줌
    return count

n, m = map(int,input().split()) # 컴퓨터의 수, 신뢰관계의 수

graph = [[] for _ in range(n + 1)] # 신뢰관계 그래프
for _ in range(m):
    a, b = map(int,input().split()) # A가 B를 신뢰
    graph[b].append(a)              # 반대 방향으로 간선 연결

max_count = -1e9
result = []
for i in range(1, n + 1):  # 각 노드별로 탐색
    visited = [0] * (n + 1) # 방문했음을 체크할 list
    count = bfs(i)          # 탐색할 수 있는 노드의 수 
    max_count = max(max_count, count) # 최댓값 구함
    result.append((i, count)) # 노드 번호별 count 값 저장
 
for i in result:
    if i[1] == max_count: # 만약 count 값이 최댓값과 같다면
        print(i[0], end = ' ') # 해당 노드 번호 출력