[백준] #7576 토마토 python

 

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

7576번: 토마토

📕 설명 📕

토마토 문제로, bfs로 matrix를 순회하는 문제이다.

 

bfs로 토마토 농장을 순회하여 대각선이 아닌 상하좌우 좌표를 활용해서 1 주변의 것들을 1로 만든다.

 

-1인 것은 비어있는 것, 0은 토마토가 익지 않은 것, 1은 토마토가 익은 것이다.

 

🧑🏻‍💻 나의 풀이 🧑🏻‍💻

 

 

from collections import deque
M, N = map(int, input().strip().split(' '))

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

queue = deque([])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(N):
    for j in range(M):
        if tomato_matrix[i][j] == 1:
            queue.append([i, j])

def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0 <= nx < N and 0 <= ny < M and tomato_matrix[nx][ny] == 0:
                tomato_matrix[nx][ny] = tomato_matrix[x][y] + 1
                queue.append([nx, ny])

bfs()
result = 0
for i in tomato_matrix:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    result = max(result, max(i))
print(result - 1)