문제

코드

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

m,n = map(int,input().split())

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

queue = deque()
graph=[]

for i in range(n):
    graph.append(list(map(int, input().rstrip().split())))

#붙이기 

#익은토마토 조사 
for i in range(n):
    for j in range(m):
        if graph[i][j]==1:
            queue.append([i,j])

def bfs():
  while queue:
      a,b = queue.popleft() #i.j삽입 
      for i in range(4):
          cx = a+dx[i]
          cy = b+dy[i]
          if 0<=cx<n  and 0<=cy<m and graph[cx][cy]==0: 
              graph[cx][cy] = graph[a][b] + 1 #시간 더해나감 
              queue.append([cx,cy])
# print(graph)
bfs()
flag = 1 # 1 익음 0 안익음  
time = -2 
# print(graph)
for j in graph:
    for k in j:
        if k==0: #익지 않은것이 존재 
            flag =0 #안익음... 
        time =max(time,k)

if time == 1 : #최댓값이 1 #다익음   
    print(0)
elif flag ==0: #안익은게 있음/// 
    print(-1)
else :
    print(time - 1) #1초부터 시작하니 1빼줌 

해설

이 문제 역시 BFS로 진행 해준다.
그 이유는 순차적으로 양옆으로 토마토를 익혀가게 해야하기 때문이다.
그리고 상하좌우를 보기 위해서 방향벡터를 다시 가져와서 사용해주었다.
그 후 값을 입력받고 BFS를 위해 덱으로 만들어둔 큐에 그 요소의 인덱스값을 삽입한다.

BFS

큐를 하나씩 빼주면서 그 큐의 상하좌우에 익지 않은 토마토가 있다면 익혀나가는데 이 토마토에 들어가야 하는 값은 그 전에 있었던 토마토에 저장된 값에 +1을 해주면서 진행된다!!
비슷한 형식이 보이지않는가?!?!
이는 앞서 풀었던 문제에서 숨바꼭질에서는 초를 저장해주듯이 초를 점점 늘려가는형식이다 !
그렇게 1이 들어있던 요소들이 늘어나고 난 후 2가들어있는 요소들이 쭉쭉 퍼져나가는 전형적인 BFS이다.

이렇게 한 후 마지막에 전체리스트를 조사하면서 안익은 토마토가 있다면 flag =0을 저장한다.
그리고 time이라는 변수에는 시간의 최댓값을 출력하게 하는데, 만약 모두 익어져있는 상태에서 시작한다면 time에는 1이 저장될것이다.
그에 반해 하나씩 익어간다면 time은 그 시간의 최댓값이 저장될것이다.

그러므로 마지막 조건문을 사용하여 3가지 케이스중 맞는 케이스를 찾아 출력한다.