[BOJ] 7576 토마토

# 7576번 문제 
# 1은 익은 토마토 0은 익지않은 토마토

N,M = map(int,input().split())

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

dx = [-1,1,0,0]
dy = [0,0,1,-1]
tomatocnt = 0
total = N*M
tomato = []
for x in range(M):
    for y in range(N):
        if tomatoarray[x][y] == 1:
            tomato.append((x,y))
            tomatocnt += 1
        elif tomatoarray[x][y] == -1:
            total -= 1
result = -1
day = 0
if total == tomatocnt:
    result = 0
else:
    while tomato:
        new_tomato = []
        for x,y in tomato:
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<M and 0<=ny<N:
                    if not tomatoarray[nx][ny]:
                        tomatoarray[nx][ny] = 1
                        new_tomato.append((nx,ny))
                        tomatocnt += 1


        day += 1
        if tomatocnt == total:
            result = day
            break
        if len(new_tomato):
            tomato = [row[:] for row in new_tomato]
        else:
            result = -1
            break



print(result)

익은 토마토를 기준으로 상하좌우로 인접한 토마토들만 익는다. 

 

1일차의 토마토가 익힌 인접 토마토들이 2일차에 새로운 토마토들을 익히게 된다.

그러므로 1일차의 토마토들은 필요 없어진다.

 

이런한 점을 이용해, 반복문을 통해 새롭게 익은 토마토들을 찾아내고, 그때 토마토 개수를 늘려준다. 

 

그리고 난뒤 전체 행렬의 크기와 토마토 개수가 같으면 반복문을 탈출하고,

 

새롭게 익은 토마토들이 있으면, 더 익힐 가능성이 있으므로, 그 리스트를 복사해서 반복해준다.

 

하지만 새롭게 익은 토마토들이 없으면, 더이상 익힐 가능성이 없으므로, 반복문을 탈출해서 -1을 출력해주면 된다.