백준, 토마토, 7576, 파이썬

[유형]

bfs

 

[문제링크]

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

 

[요약]

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

[문제풀이]

import sys
# sys.setrecursionlimit(10**7)
from collections import deque
def input():
    return sys.stdin.readline().rstrip()

def bfs():
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m and graph[nx][ny]==0:
                graph[nx][ny] = graph[x][y] + 1
                q.append((nx,ny))

dx = [0,0,-1,1]
dy = [-1,1,0,0]

m,n = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))

q = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            q.append([i, j])

bfs()

day = 0
for row in graph:
    for r in row:
        if r == 0:
            print(-1)
            exit()
    day = max(day,max(row))

print(day-1)