[백준] 7576번 토마토 - 파이썬

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

7576번: 토마토

 

from collections import deque
def BFS(start):
    global matrix, days, W, H

    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    q = deque()
    for s in start:
        i, j = s[0], s[1]
        q.append([i, j])
        matrix[i][j] = 1
    while q:
        days += 1
        for _ in range(len(q)):
            y, x = q.popleft()
            for i in range(4):

                nx = x + dx[i]
                ny = y + dy[i]

                if 0<=nx<W and 0<=ny<H and matrix[ny][nx] == 0:
                    q.append([ny, nx])
                    matrix[ny][nx] = 1
                    
        #for row in matrix:
        #    print(row)
        #print()


    for i in range(H):
        for j in range(W):
            if matrix[i][j] == 0:
                return -1
    return days

W, H = map(int, input().split())
matrix = []
days = -1
for i in range(H):
    matrix.append(list(map(int, input().split())))
start = []
for i in range(H):
    for j in range(W):
        if matrix[i][j] == 1:
            start.append([i,j])

print(BFS(start))