이번 문제는 BFS를 통해 해결하였다. 몇달전에 C++로 풀어본 문제였는데, 파이썬으로 다시 한번 풀어보았다. 이 문제의 경우 익은 토마토에 대해서 모든 탐색을 진행하면 시간초과가 발생한다. 그렇기 때문에 새롭게 익은 토마토들로 큐를 갱신해가며 BFS탐색을 진행해야 한다. 이러한 방식으로 문제를 해결하였다.

Code

import copy
from collections import deque
m, n=map(int, input().split())
tomato=[list(map(int, input().split())) for _ in range(n)]
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
visited=[[1e9 for _ in range(m)] for _ in range(n)]
tomatos=deque()
def bfs():
    global tomatos
    new_tmt=deque()
    while tomatos:
        y, x=tomatos.popleft()
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<n and 0<=nx<m and tomato[ny][nx]!=-1 and visited[ny][nx]>visited[y][x]+1:
                tomato[ny][nx]=1
                visited[ny][nx]=visited[y][x]+1
                new_tmt.append((ny, nx))
    tomatos=copy.copy(new_tmt)
for i in range(n):
    for j in range(m):
        if tomato[i][j]==1:
            tomatos.append((i, j))
            visited[i][j]=0
while tomatos:
    bfs()
answer=0
for i in range(n):
    for j in range(m):
        if tomato[i][j]>0:
            answer=max(answer, visited[i][j])
        elif tomato[i][j]==0:
            answer=-1
            print(answer)
            quit()
print(answer)