[백준 7576 토마토 ] 파이썬 풀이

# 7576 토마토
# bfs
# Pypy3 912ms
 
def count_zero(board):  # 0이 몇개 있는지 파악합니다.
    count = 0
    for i in range(M):
        for j in range(N):
            if board[i][j] == '0':
                count += 1
    return count
 
 
# BFS 이동
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
 
 
def move(x, y):
    global value
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
 
        if 0 <= nx < M and 0 <= ny < N :
            if board[nx][ny] == '0':
                board[nx][ny] = '1'
                value -= 1  # 시간을 줄이기 위해 0의 개수를 실시간으로 파악
                LST_temp.append((nx, ny))  # 시간을 줄이기 위해 새롭게 탐색해야 하는 곳 파악
 
    board[x][y] = '2'  # 시간을 줄이기 위해 기존 위치 제거
 
 
N, M = map(int, input().split())
board = [input().split() for _ in range(M)]
 
count = M * N
prev = 0
c = 0
value = count_zero(board)
 
LST = []
LST_temp = []
for i in range(M):  # 처음에 1인 곳 찾기
    for j in range(N):
        if board[i][j] == '1':
            LST.append((i, j))
 
while True:  # 0의 개수가 변하지 않을 때까지
    c += 1
    prev = value
    for p in LST:
        move(p[0], p[1])
    LST = LST_temp[:]
    LST_temp = []
 
    count -= 1
    if value == prev:
        break
 
if value != 0:
    print(-1)
else:
    print(c - 1)