[BOJ] 7576. 토마토

📌 문제 제목

문제 링크: BOJ 7576

---

🗒️ 문제 설명

토마토를 격자 모양의 상자에 보관한다.

익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.

토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶다.

시간 제한: 1초

메모리 제한: 256MB

2 <= M, N <= 1,000

---

💡 문제 해결 아이디어

• 이차원 for 문을 돌며 초기에 익은 토마토들의 위치를 큐에 저장한다.
• 큐가 빌 때 까지 BFS를 수행한다.
• 이차원 for문을 돌며 dist의 최대값을 구한다.
• 이차원 for문을 돌 때 dist가 -1이면서 익지 않은 토마토가 있으면 -1을 출력한다.

---

⌛️ 시간 복잡도

• O(NM)

---

✅ 최종 코드

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

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

queue = deque([])
dist = [[-1] * M for _ in range(N)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 초기 세팅
for i in range(N):
    for j in range(M):
        if graph[i][j] == 1:
            queue.append((i, j))
            dist[i][j] = 0

while queue:
    xp, yp = queue.popleft()
    for dx, dy in direction:
        nx, ny = xp + dx, yp + dy
        if not (0 <= nx < N and 0 <= ny < M):
            continue
        if graph[nx][ny] == 0 and dist[nx][ny] == -1:
            queue.append((nx, ny))
            dist[nx][ny] = dist[xp][yp] + 1

mx = 0
for i in range(N):
    for j in range(M):
        if dist[i][j] == -1 and graph[i][j] == 0:
            print(-1)
            exit(0)
        mx = max(mx, dist[i][j])

print(mx)