[白俊][Python]7576号トマト

[白俊]7576号トマト

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

問題の説明📖

チョルスのトマト農場にはトマトを保管する大きな倉庫がある.トマトは下図のように1つずつ四角い格子に入れて倉庫に保管しています.

倉庫に保管されているトマトの中には、熟しているものもあれば、まだ熟していないものもあります.1日保管した後、熟したトマトに隣接する未熟のトマトは、熟したトマトの影響を受けて成熟する.1つのトマトの隣接する場所は、左、右、前、後の4つの方向に位置するトマトを意味する.対角線方向に影響を与えないトマトは、トマトが自分で成熟しないと仮定します.哲洙は倉庫に保管されているトマトが何日で熟れるか、最低日数を知りたいと思っている.
倉庫にトマトのチェックボックスの大きさ、熟したトマトと未熟なトマトの情報を保管している場合、数日後には、トマトが熟しているかどうか、最低日数を求めるプログラムを作成します.しかし、箱のいくつかの格にはトマトが入っていないかもしれません.
入力
最初の行は、ボックスのサイズを表す2つの整数M,Nを与える.Mは箱の横格子数,Nは箱の縦格子数を表す.しかし,2≦M,N≦1000であった.2行目から、1つの箱に保存されているトマトの情報が提供されます.つまり、2行目からN行目まで、箱の中のトマトの情報が出てきます.1本の線上で、箱の横線のトマトの状態はM個の整数である.整数1は熟したトマトを表し、整数0は未熟のトマトを表し、整数-1はトマトを含まない格子を表す.
トマトが1つ以上ある場合にのみ入力します.
しゅつりょく
トマトがすべて熟成した最小日付を印刷します.保存からすべてのトマトが熟成している場合は0を、トマトが熟成していない場合は-1を出力します.
I/O例

質問へのアクセス💡

1.BFSによる解析
2.隣接する上下左右の位置を一度移動すると、行列[nx][ny]=行列[x][y]+1
3.for文が0であるかどうかを確認し、0である場合-1を検索し、0である場合BFSに変更された最大値を検索して出力する

問題を解く💡

from collections import deque
# deque함수가 시간복잡도가 O(1)이고, pop(0) 시간복잡도가 O(n)이므로 deque함수 사용이 좋음.

M, N = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]

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

queue = deque()
res = 0

for i in range(N):
    for j in range(M):
        if matrix[i][j] == 1:
            queue.append((i,j))

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue

            if matrix[nx][ny] == 0:
                matrix[nx][ny] = matrix[x][y] +1
                queue.append((nx,ny)) 

BFS()

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