[Python] 1325번 효율적인 해킹

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

1325번: 효율적인 해킹

---

 

24/02/07

 

 

간단한 그래프 탐색 문제로, 좀 더 최적화를 시킬 수도 있을 법 한 문제이다.

 

Python3로는 통과하지 못했고, pypy로 통과한 코드를 올린다. 

---

 

문제 접근 방식:

 

 

A가 B를 신뢰한다는 것은 B를 해킹한다면 A를 해킹할 수 있다는 뜻이다.

 

즉, 그래프로 따지면 단방향 간선을 준 셈인데, 문제에서 요구하는 것은 가장 많은 해킹을 할 수 있는 컴퓨터의 번호를 출력하는 것이다.

 

시간제한이 5초로 넉넉함을 확인하여, BFS를 모든 노드 별로 수행하는 풀이를 생각했다.

 

노드는 최대 $10,000$개까지이고, BFS를 한 번 수행할 때 최대 $\mathcal{O}(N+E)$의 시간 복잡도가 소요되므로, $\mathcal{O}(N^2 + NE)$의 시간 복잡도보다 더 작은 시간 복잡도로 문제가 해결될 것이라고 추측했다.

 

Python3로는 통과하지 못했지만 Pypy로는 통과했다. Python3로 통과하는 방법이 무엇인지는 모르나, 아직 아무도 통과하지 못한 것으로 봐서는 이 문제가 Python3로 통과하는 것이 거의 불가능한 문제가 아닐까 싶다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1325번 효율적인 해킹
# 그래프 탐색
'''
접근 방법:
A가 B를 신뢰 = B해킹 -> A해킹
BFS를 N번 수행해보자.
'''
import sys
input = sys.stdin.readline
from collections import deque

def BFS(graph, N, start):
    visited = [0 for _ in range(N+1)]
    visited[start] = 1
    queue = deque()
    queue.append(start)
    hacked = 1
    while queue:
        node = queue.popleft()
        for near_node in graph[node]:
            if visited[near_node] == 0:
                visited[near_node] = 1
                queue.append(near_node)
                hacked += 1
    return hacked

def main():
    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)

    ans = []
    max_hacked = 0
    for start in range(1, N+1):
        hacked = BFS(graph, N, start)
        if hacked > max_hacked:
            ans = []
            ans.append(start)
            max_hacked = hacked
        elif hacked == max_hacked:
            ans.append(start)
    print(*ans)

main()