백준 파이썬 7576 토마토

백준 링크:https://www.acmicpc.net/problem/7576

7576번: 토마토

미로 탐색과 비슷한 유형의 BFS문제이다.

처음에는 시간 초과가 나오길래 뭔가 잘못되었다 생각했는데.

처음 배열 지정할때 1이 여러개있으면 QUEUE에 있는 수를 꺼내는데 많은 시간이 걸리기 떄문에

DEQUE를 사용해 시간 단축을 하였다.

import sys
from collections import deque

n,m=map(int,input().split())
queue=deque([])
s=[]
for i in range(m):
    s.append(list(map(int,sys.stdin.readline().split())))
    for j in range(n):
        if s[i][j] == 1:
            queue.append([i,j])

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

while queue:
    x,y = queue.popleft()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < m and 0 <= ny < n:
            if s[nx][ny] == 0:
                queue.append([nx,ny])
                s[nx][ny] = s[x][y] + 1

max_s = 0

for i in s:
    for j in i:
        if j == 0:
            print(-1)
            exit()
        max_s = max(max_s,j)
print(max_s-1)