7569번: 토마토

본 글의 내용은 절대적으로 좋은 코드라는 보장이 없습니다. 글을 읽어보시다가 "이 사람은 이런 식으로 짰구나. 되게 허접하게 짰네?" 라는 생각이 드시면 댓글을 통해서 좋은 가르침과 의견을 주시면 감사합니다!!

---

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

7569번: 토마토

기본 아이디어

• 기본적인 아이디어는 전에 올린 7576 토마토에서 z축 방향의 코드를 추가한 것에 불과하다
• 하지만, 그보다 더 큰 위협이 있었으니...

import sys
sys.stdin = open('input.txt', 'r')
from collections import deque

M, N, H = map(int, sys.stdin.readline().split())
box = []

Q = deque()

dx = [0, 0, -1, 1, 0, 0]
dy = [-1, 1, 0, 0, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
min_day = 0

for h in range(H):
    floor = []
    for n in range(N):
        line = list(map(int, sys.stdin.readline().split()))
        for m in range(M):
            if line[m] == 1:
                Q.append([m, n, h, 0])
        floor.append(line)
    box.append(floor)

while Q:
    v = Q.popleft()

    for d in range(6):
        new_x = v[0] + dx[d]
        new_y = v[1] + dy[d]
        new_z = v[2] + dz[d]

        if -1 < new_x < M and -1 < new_y < N and -1 < new_z < H and not box[new_z][new_y][new_x]:
            box[new_z][new_y][new_x] = 1
            new_day = v[3] + 1
            Q.append([new_x, new_y, new_z, new_day])
            if new_day > min_day:
                min_day = new_day

for h in range(H):
    for n in range(N):
        if 0 in box[h][n]:
            print(-1)
            sys.exit()
else:
    print(min_day)

유의사항

• 위 코드를 Python3에서 돌리면 시간초과가 되어서 돌아가지 않습니다.
• 그렇게 찾고 찾다고 PyPy3으로 돌리면 코드는 돌아간다고는 해서 돌렸지만...
• 어쨌든 코드가 다소 연산을 많이 차지하기 때문에 Python3에서 돌아가지 않는다는 뜻이기 때문에 훌륭한 알고리즘 코드라고 보기에는 어려움이 있지 않나 싶습니다.
• 여러 방면에서 찾아보았으나 시간을 줄이는 방법을 찾지 못 했습니다.
• 혹시나 방법을 아시는 분은 저에게 큰 깨달음을 주소서...