[백준] 7576번:토마토 (python 파이썬)

문제

www.acmicpc.net/problem/7576

7576번: 토마토

 

풀이

일반 que로 풀었더니 계속 시간초과가 났다.

deque로 풀고 해결 ㅠㅠ 흑

 

소스코드

import sys
from collections import deque
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
    ans = 0
    while que:
        flag=0
        for _ in range(len(que)):
            y, x = que.popleft()
            for i in range(4):
                nowx, nowy = x+dx[i], y+dy[i]
                if 0<=nowx<m and 0<=nowy<n and arr[nowy][nowx]==0:
                    arr[nowy][nowx] = 1
                    flag=1
                    que.append([nowy, nowx])
        if flag==1:
            ans+=1
    return ans
    

m, n = map(int, input().split())
arr = []
que = deque()
for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(m):
        if tmp[j]==1:
            que.append([i, j])
    arr.append(tmp)
ans=bfs()
for i in range(n):
    for j in range(m):
        if arr[i][j] == 0:
            print(-1)
            exit()

print(ans)