[BOJ] 7576번 : 토마토

1. 문제

7576번: 토마토

문제

• 익은 토마토에 인접한 토마토도 하루 뒤 익는다.
• 인접 : 상하좌우
• 혼자 익는 경우는 없다.
• 보관된 토마토가 모두 익는 최소 일 수

입력 조건

• m : 가로 칸 수 (열), n : 세로 칸 수 (행)
• 2 ≤ m, n ≤ 1000
• 1 : 익은 토마토
• 0 : 안 익은 토마토
• -1 : 토마토가 없는 칸

출력 조건

• 모든 토마토가 익는 최소 날짜
• 이미 모두 익어있는 상태면 0 출력
• 모두 익을 수 없을 시 -1 출력

2. 알고리즘

• BFS
• 각 칸에 토마토가 익는데 걸린 날짜 저장
• 탐색 후 토마토 창고에서 가장 큰 수(날짜) 반환

3. 소스코드

# BFS 탐색을 위한 자료구조 queue
from collections import deque

m, n = map(int, input().split()) # n * m 창고
graph = [list(map(int, input().split())) for _ in range(n)]

# 상하좌우 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 모든 토마토가 이미 익은 상태인지 확인
tomato_count = 0
for tomatoes in graph:
    tomato_count += sum(tomatoes)

# 이미 모든 토마토가 익은 경우 0 출력
if tomato_count == n * m:
    print(0)
    exit()

# 익은 토마토 queue에 저장
q = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            q.append((i, j))

# bfs 함수 정의
def bfs():
    while q:
        x, y = q.popleft()

        # 인접 토마토 확인
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            # 행렬 인덱스를 벗어난 경우
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue

            # 토마토가 없는 칸인 경우
            if graph[nx][ny] == -1:
                continue

            # 익지 않은 토마토인 경우
            if graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1 # 익는데 걸린 날짜 저장
                q.append((nx, ny)) # queue에 push

bfs()
ans = -99999

for tomatoes in graph:
    if 0 in tomatoes: # 안 익은 토마토(0)가 있는 경우
        ans = -1 # -1 출력
        break
    ans = max(ans, max(tomatoes)) # 최댓값(날짜) 찾기

print(ans if ans == -1 else ans - 1)

4. 주의

답을 출력할 때 -1을 하는 이유

처음 하루가 지날 때 익은 토마토(1)에 인접한 토마토가 익을 때 값이 익은 토마토의 값에 +1인 2가 저장된다. 따라서 실제 지난 날짜보다 1이 크기 때문에 -1을 해서 실제로 지난 날짜를 출력하는 것이다.