[백준] 1325번 효율적인 해킹 BFS/DFS Python - pypy3

문제와 입출력

시간 복잡도와 공간 복잡도

문제 조건에 따르면 최대 노드의 개수는 10000 개, 최대 간선의 개수는 100000 개였다. 최악의 시간 복잡도가 O(110000)이고 시간 제한이 5초라서 시간 복잡도는 여유롭다는 판단을 내렸다. 하지만, 노드랑 간선의 개수가 1000개를 넘어가기에 DFS로 구현하면 RecursionError가 발생하기에 BFS로 구현하기로 마음먹었다.

---

자연어 알고리즘과 코드

1. 방향 그래프를 만든다.

2. 시작 노드를 1~n 순차적으로 설정하여 BFS 탐색을 한다.

3. 시작 노드를 x으로 설정하여 BFS 탐색을 할 때, 탐색된 노드의 개수가 해킹할 수 있는 컴터의 개수이다.

4. 3번의 정보를 리스트 a에 담고 max를 찾는다.

5. 리스트a에서 max를 가진 요소의 인덱스 탐색하고, 그 인덱스를 오름차순으로 출력한다.

import sys 
from collections import deque

# 정보를 받아 방향 그래프 graph를 생성한다.
input = sys.stdin.readline
n,m = map(int, input().split())
graph = [[] for _ in range(n+1)]

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

# bfs 탐색
def bfs(graph,v):
    visited = [False] * (n+1)    
    infect = 0 # 감염된 컴퓨터의 수
    queue = deque([v])
    visited[v] = True

    while queue:
        cur = queue.popleft()
        for i in graph[cur]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
                infect += 1 # 탐색됨 = 감염됨 -> 감염 + 1
    
    return infect # 시작 노드가 x일 때, 감염된 컴퓨터의 수

# 시작 노드가 인덱스 i일 때 감염된 컴퓨터의 수
cnt = [bfs(graph,i) for i in range(1,n+1)]
cnt_max = max(cnt)
# 정답 출력
[print((i+1), end=" ") for i in range(0,n) if cnt_max == cnt[i]]

---

애초에 python으로 성공할 수 없었던 문제였다. pypy3를 사용하니 되더라

문제 로직은 빨리 찾아냈으나 시간 초과가 문제였다. 코드에 따르면 cnt = [bfs(graph,i) for i in range(1, n+1)  이 부분에서 O(n^3)가 나오기에 시간초과가 나올만 하다고 생각했다. 하지만, 문제를 풀면 풀수록 bfs에서 시작 노드를 차례 차례 다른 노드로 설정하고, BFS 탐색을 하기 위해서는 O(n^3)가 필연적이었다. 그리고 시간제한이 5초인 것이 더 이상해 보였다. 5초면 사실상 시간 제한은 신경쓰지 말라는 것처럼 들렸기 때문이다. 이런 의문점을 가지고 나는 구글링을 시작했다. 그런데 알고보니....

파이썬으로 풀 수 없을 수도 있다?

이 문제는 파이썬으로 풀 수 없다는 사실을 알게되었다. 학교에서 간혹 교수님들이 "파이썬은 느리다."라고 말씀하셨던게 체감되었던 순간이었다. 구글님의 말씀으로는 python3로 말고 pypy3를 쓰라고 하셨다. pypy3는 반복되는 코드를 캐싱하는 기능이 있어 python3보다 시간 면에서 우위를 가진다. 결과적으로, pypy3를 써서 문제를 검사받아보니 여전히 오래 걸리긴 했지만 문제는 통과되었다.

---

3줄 소감(배운 점)

1. pypy3는 재사용 되는 코드를 캐싱하기에 Python3보다 시간 면에서 우위를 가진다.

2. 노드의 개수와 간선의 개수가 1000개를 훌쩍 넘기에 BFS 탐색을 이용한다.

3. 입출력 속도를 빠르게 하기 위해 sys.stdin.readline을 사용했다.