[BOJ]7576_토마토

토마토

풀이

어려웠던 점
토마토가 여러 개 있을 때
동시에 근처 토마토가 익어가야 한다.

문제에서 '최소일수', '주변의 토마토들을 익힘' 이라는 말을 봐서 bfs 문제임을 알았다.
dfs를 쓰면 안되는 문제였다. 깊이 들어갈 일이 없기 때문이다.

코드

from collections import deque
import sys
sys.stdin =open('in.txt','rt')
input = sys.stdin.readline 
m,n = map(int,input().split())

box = [list(map(int,input().split())) for _ in range(n)]
queue = deque()
answer = 0 
for i in range(n):
    for j in range(m):
        if box[i][j] == 1 : # 1 부터 시작 
            queue.append((i,j))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while queue : 
    x,y = queue.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and box[nx][ny] == 0 : 
            box[nx][ny] = box[x][y] + 1 
            queue.append((nx,ny))
        

# 0 이 남아 있으면 -1 출력 
for i in box : 
    if 0 in i : 
        answer = -1
        print(-1)
        break
    else : 
        answer = max(answer,max(i))


if answer != -1 : 
    print(answer-1)