[백준] 7576 토마토

📖 문제

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

💻 내 코드

import sys
from collections import deque

m, n = map(int, sys.stdin.readline().split())

box = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

queue = deque([])

for i in range(n):
    for j in range(m):
        if box[i][j] == 1:
            queue.append((i, j))


def tomato():
    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:
                if box[nx][ny] == -1:
                    continue
                if box[nx][ny] == 0:
                    queue.append((nx, ny))
                    box[nx][ny] = box[x][y] + 1

tomato()
flag = False
for i in range(n):
    for j in range(m):
        if box[i][j] == 0:
            flag = True
            break

res = max(map(max, box))
if flag == True:
    print(-1)
elif res == 1:
    print(0)
else:
    print(res - 1)

💡 풀이

• bfs 이용
• 저장된 수 중 1이 있으면 덱에 추가
• 모두 추가하고 bfs를 구현한 tomato 함수를 실행한다
• tomato 함수
  • 가장 왼쪽의 원소를 뽑아 각각 x, y에 저장
  • 상하좌우를 돌면서 배열 인덱스 범위 내인지 확인
  • 만약 확인한 수가 -1이라면 토마토가 없으므로 넘김
  • 0이라면 익어야 하는 토마토임
  • 토마토가 익는 최소 일수를 구해야 하므로 일수를 구하기 위해 현재 수+1을 해준다
• 마지막에 출력시 1부터 시작해서 +1을 했으므로 배열 내 최댓값에서 1을 빼주면 토마토들이 모두 익는 최소 일수가 된다