문제 7576

정답

from collections import deque
import sys
input = sys.stdin.readline

M, N = map(int, input().split())
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))

queue = deque()
def BFS():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    while queue:
        now = queue.popleft()
        for k in range(4):
            x, y = now[0] + dx[k], now[1] + dy[k]
            if 0 <= x < N and 0 <= y < M:
                if board[x][y] == 0:
                    board[x][y] = board[now[0]][now[1]] + 1 # 현재 일수 +1
                    queue.append((x, y))
# 큐에 토마토 위치를 미리 저장하여 시간초과 방지
for i in range(N): 
    for j in range(M):
        if board[i][j] == 1:
            queue.append((i, j))

BFS()
if any(0 in r for r in board): print(-1)  
else: print(max(map(max, board))-1)

풀이

1. 토마토 위치 모두 확인

2. 위아래왼오 4방향으로 확인하며 익지 않은 토마토에 현재 일수+1하여 저장

3. board에 있는 최대값을 출력

4. 예외 처리
   만약 덜 익은 토마토가 한 개라도 있다면 -1 출력
   아니면 board의 최대값-1 출력(시작일수가 1이기 때문)
   참고로 모든 토마토가 익어있는 경우, BFS() 에서 큐에서 삭제만 하게 되고 현재 일수+1을 하지 않음

제출