[백준] 7576. 토마토

문제

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

7576번: 토마토

설계

- flood fill

- 토마토가 모두 익는 최소 날짜를 구하여야 하기에 DFS도 생각해봤으나 N, M의 수가 너무 커서 불가능

- flood fill을 이용하여 아직 익지 않은 곳에 이전보다 1 큰 숫자를 누적하며 넣어주고 마지막에 max 값을 찾아 소요일을 확인한다.

- 생각보다 코드가 길게 나왔다. 다음에는 더 줄이도록 해봐야겠다.

from collections import deque

M, N = map(int, input().split())  # M : 상자의 가로칸수 / N : 세로 칸수
arr = [list(map(int, input().split())) for _ in range(N)]

q = deque()
answer = 0

sumV, flag = 0, 0
for i in range(N):       # 처음 모든 토마토가 익어있는 상태인지 확인
    for j in range(M):
        if arr[i][j] == 1:
            sumV += 1
        else:
            break

if sumV == M*N:   # 처음 토마토가 모두 1개씩 M*N 개수만큼 차있는지 확인
    answer = 0
    flag = 1    # 처음부터 모든 토마토가 익어있는 상태이면 flag on


for i in range(N):      # 익은 토마토 자리 확인
    for j in range(M):
        if arr[i][j] == 1:
            q.append((i, j))

while q:        # 시간이 지날수록 익는다.
    x, y = q.popleft()
    for i in range(4):
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            if arr[nx][ny] == 0:
                arr[nx][ny] = arr[x][y] + 1     # 이전보다 1 큰 숫자를 넣어준다.
                q.append((nx, ny))

for i in range(N):
    for j in range(M):
        if arr[i][j] == 0:      # 모두 익지 못하는 상황
            answer = -1
            flag = 1    # 최댓값을 구하지 않고 넘어가게 하기

if flag == 0:
    for i in range(N):      # 최소일수 중 최댓값 확인
        answer = max(max(arr[i]), answer)
    answer -= 1     # 횟수를 구해야하는데 1부터 시작 했으므로 1을 빼준다.
print(answer)