[BOJ] 18405번: 경쟁적 전염 (파이썬)

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

18405번: 경쟁적 전염

---

시험관에 존재하는 바이러스를 오름차순으로 목록에 넣고 하나씩 꺼내어 전파 결과를 적용합니다.

• 바이러스의 종류와 위치 정보, 그리고 시간 정보를 포함하는 배열 virus 을 준비합니다
• 바이러스의 전파는 번호가 낮은 순으로 이루어지기에 정렬을 수행합니다
• virus를 deque로 변환하고 하나씩 꺼내어 4방향으로 전파를 수행합니다
  • 다른 바이러스가 존재하거나 시험관을 벗어나는 경우 전파가 일어나지 않습니다
  • 다음에 전파될 바이러스는 현재 시간에 1을 더하여 virus에 추가합니다

 

import sys
from collections import deque

n, k = map(int, sys.stdin.readline().rstrip().split())
testbed = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
s_last, x_last, y_last = map(int, sys.stdin.readline().rstrip().split())

dy = (1, 0, -1, 0)
dx = (0, 1, 0, -1)

virus = []
for i in range(n):
    for j in range(n):
        if testbed[i][j]:
            virus.append((testbed[i][j], 0, i, j))

virus.sort()
dq = deque(virus)
while dq:
    v, s, y, x = dq.popleft()
    if s == s_last:
        break
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if ny < 0 or ny >= n or nx < 0 or nx >= n:
            continue
        if testbed[ny][nx]:
            continue
        testbed[ny][nx] = v
        dq.append((v, s + 1, ny, nx))

print(testbed[x_last - 1][y_last - 1])

---

다음의 코드는 시간초과로 오답처리되었습니다.

• for 구문을 통해 바이러스를 순서대로 탐색하지 않고 virus에 모두 추가한 뒤에 sort를 적용한 경우 시간 초과가 발생하지 않았습니다. 
• 바이러스 정보가 담긴 배열 virus에 바이러스의 번호 순서대로 추가하기 위하여 for 구문을 통해 검색하는 부분에서 많은 시간이 소비된 것으로 보입니다.

# 시간초과
import sys
from collections import deque

n, k = map(int, sys.stdin.readline().rstrip().split())
testbed = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
s_last, x_last, y_last = map(int, sys.stdin.readline().rstrip().split())

dy = (1, 0, -1, 0)
dx = (0, 1, 0, -1)

virus = []

for v in range(k):
    for i in range(n):
        for j in range(n):
            if testbed[i][j] == v + 1:
                virus.append((v + 1, 0, i, j))

dq = deque(virus)
while dq:
    v, s, y, x = dq.popleft()
    if s == s_last:
        break
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if ny < 0 or ny >= n or nx < 0 or nx >= n:
            continue
        if testbed[ny][nx]:
            continue
        testbed[ny][nx] = v
        dq.append((v, s + 1, ny, nx))

print(testbed[x_last - 1][y_last - 1])