[백준] 7576번 토마토 [Python]

• 문제 : https://www.acmicpc.net/problem/7576
• BFS
• deque의 popleft()를 쓰지않고 pop(0)으로 했을 때 시간초과가 뜬다.

from collections import deque

n, m = map(int, input().split())
tomato = []

for i in range(m):
    tomato.append(list(map(int, input().split())))

Q = deque([])
zero = 1

for i in range(m): # 4
    for j in range(n): # 6
        if tomato[i][j] == 1: # 익어있는 토마토들의 위치를 먼저 큐에 저장
            Q.append([i, j])
        if tomato[i][j] == 0: # 안익은게 있으면
            zero = 0    # 0 으로 바꾼다

if zero == 1: # 처음부터 다 익어있으면 0출력하고 끝냄
    print(0)
    exit()

while Q: # BFS
    zx, zy = [0, 0, 1, -1], [1, -1, 0, 0]

    x, y = Q.popleft()
    
    for i in range(4):
        nx, ny = x + zx[i], y + zy[i]
        
        if 0 <= nx < m and 0 <= ny < n and tomato[nx][ny] == 0:
            tomato[nx][ny] = tomato[x][y] + 1
            Q.append([nx, ny])

for i in range(m): # BFS 끝냈는데 안익은 토마토가 있으면 -1
    for j in range(n):
        if tomato[i][j] == 0:
            print(-1)
            exit()

print(tomato[x][y] - 1)