[백준] 7576 토마토

문제

보관 후 하루 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토이다. 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 구해야한다.

구현

[코드 설명]
최소 일수를 구하는 문제 이므로 bfs를 이용하면 된다. 큐에는 익은 토마토가 있는 좌표를 넣어준다. 큐에서 하나씩 빼내면 왼쪽, 오른쪽, 위, 아래를 비교한 후 안 익은 토마토가 있는 경우는 며칠 째에 익었는지 1을 증가시켜주고 큐에 넣어준다.
[코드]

import sys
from collections import deque

M, N=map(int, input().split())
tomatos=[]
# 상하좌우
dx=[-1, 1, 0, 0]
dy=[0, 0, 1, -1]
queue=deque()
answer=0
for i in range(N) :
    tomatos.append(list(map(int, sys.stdin.readline().split())))

#익은 토마토가 있는 곳 위치 큐에 삽입해둠
for i in range(N):
    for j in range(M) :
        if tomatos[i][j]==1:
            queue.append((i, j))

def bfs():
    while queue:
        x, y=queue.popleft()
        for i in range(4) :
            nx, ny=x+dx[i], y+dy[i] #상하좌우 확인

            if nx < 0 or nx >=N or ny < 0 or ny>=M :
                continue
            if tomatos[nx][ny]==0 :#상하좌우에 안익은 토마토가 있는 경우
                tomatos[nx][ny]=tomatos[x][y]+1 #며칠째에 익었는지
                queue.append((nx, ny))
bfs()
for i in tomatos:
    for j in i :
        if j==0 : #안익은 토마토가 있는 경우
            print(-1)
            exit(0)
    answer=max(answer, max(i)) 
print(answer-1)