[백준] 7569. 토마토 파이썬 풀이

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

• bfs를 활용하는 문제
• 개인적으로 높이까지 주어져 3차원 배열을 사용해서 문제를 푸는 것이 까다로웠다.
• 또한, 마지막에 max 값을 찾아주는 단계에서 기존에 사용하던대로 max(map(max, check)) 와 같이 최대값을 구할 수 있을 것이라 생각하여 max()를 한번 더 씌워줬는데 최댓값이 정확히 안구해지는 경우가 있더라. 이 부분에서 반례를 찾는데 시간이 오래 걸렸고, 결국 탐색을 하며 최대값을 구하도록 변경하여 통과했다.
• 함수로 구현하지 않으면 파이썬 인터프리터로는 시간 초과가 발생한다. 시간 초과를 피하기 위해서
  • input() 대신 sys.stdin.readline()을 사용할 것.
  • 적절히 함수로 분배해줄 것
  • deque()를 사용하여 시간 복잡도를 줄일 것
  • pypy로 채점을 해봐서 로직적으로 문제가 없는지는 확인할 수 있을 것 같다.

from collections import deque
import sys

sys.stdin = open("7569_토마토_input.txt", "r")
dx = [-1, 0, 1, 0, 0, 0]
dy = [0, 1, 0, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]
m, n, h = map(int, sys.stdin.readline().split())
board = [[list(map(int, sys.stdin.readline().split())) for _ in range(n)] for _ in range(h)]
check = [[[0] * m for _ in range(n)] for _ in range(h)]
queue = deque()

for z in range(h):
    for x in range(n):
        for y in range(m):
            if board[z][x][y] == 1:
                queue.append((z, x, y))


def bfs():
    while queue:
        tmp = queue.popleft()

        for i in range(6):
            z = tmp[0] + dz[i]
            x = tmp[1] + dx[i]
            y = tmp[2] + dy[i]

            if (0 <= x < n) and (0 <= y < m) and (0 <= z < h) and (board[z][x][y] == 0) and (check[z][x][y] == 0):
                board[z][x][y] = 1
                check[z][x][y] = check[tmp[0]][tmp[1]][tmp[2]] + 1
                queue.append((z, x, y))


bfs()
flag = True
result = -2147000000

for z in range(h):
    for x in range(n):
        for y in range(m):
            if board[z][x][y] == 0:
                flag = False
            result = max(result, check[z][x][y])

if flag:
    print(result)
else:
    print(-1)