[백준/7576/파이썬] 토마토

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

7576번: 토마토

Problem

철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

 

조건

• 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 
• 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. 단, 2 ≤ M,N ≤ 1,000 이다.
• 여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 
• 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 

SOL)

동시에 토마토가 익기 때문에, 먼저 토마토들을 queue에 넣어줘야한다.

그리고, box에 일 수를 바로 기록해줘서, 기록된 일 수에서 제일 큰 걸 출력해주면 됨.

단, 안익은 토마토가 하나라도 있을 시에는, 바로 -1을 출력한다.

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

M,N = map(int,input().split())
box = [list(map(int,input().split())) for _ in range(N)]
#print(box)
visited= [[False]*M for _ in range(N)]
dx=(0,1,0,-1)
dy=(1,0,-1,0)
dq=deque()

# 토마토 위치 다 저장
for i in range(N):
    for j in range(M):
        if box[i][j] == 1:
            visited[i][j] = True
            dq.append((i,j))

def bfs():
    while dq:
        y,x = dq.popleft()
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if (0<=ny<N and 0<=nx<M) and not visited[ny][nx] and box[ny][nx] ==0:
                box[ny][nx] = box[y][x] +1
                visited[ny][nx] =True
                dq.append((ny,nx))

bfs()
ans=0
for i in range(N):
    for j in range(M):
        if box[i][j] ==0:
            print(-1)
            exit()
    ans = max(ans,max(box[i]))
print(ans-1)