15.토마토(BFS 활용)

문제 - 생략

 

문제풀이

import sys
from collections import deque
sys.stdin=open("input.txt", "r")
dx=[-1, 0, 1, 0]  
dy=[0, 1, 0, -1]
n, m=map(int, input().split())
board=[list(map(int, input().split())) for _ in range(m)]
dis = [[0]*n for _ in range(m)]
Q=deque()

for i in range(m):
    for j in range(n):
      if board[i][j] == 1: #행단위로 검색하면서 익은 토마토 발견 
            Q.append((i, j))

while Q:
   tmp=Q.popleft()
   for k in range(4):  #range의 범위만큼 자식이 생긴다
      x=tmp[0]+dx[k]
      y=tmp[1]+dy[k]
      if 0<=x<m and 0<=y<n and board[x][y] ==0:    #board[x][y] ==0의 의미 : 안 익은 토마토인 경우 
            board[x][y]=1
            dis[x][y] = dis[tmp[0]][tmp[1]] +1     #토마토가 익을 때 +1해서 날짜를 카운팅한다. 
            Q.append((x, y))
                          
flag =1
for i in range(m):
    for j in range(n):
      if board[i][j] == 0: 
            flag = 0
            
result =0
if flag ==1:
  for i in range(m):
      for j in range(n):
        if dis[i][j]> result:
          result =dis[i][j]
  print(result)

else:
  print(-1)

 

Hint

▶토마토가 익는 날짜를 표기하기 위해서 별도의 "체크리스트"를 만든다.

 

▶토마토가 차례대로 익는 것이 아니라 동시에 익어 가기 때문에 큐(Q)에 익은 토마토가 완전히 적재된 이후에 

    BFS탐색을 실시한다. 

 

 

▶board[x][y] ==0의 의미 : 안 익은 토마토인 경우를 의미한다. 
            

▶board[x][y]=1  ← 토마토를 익게 만든다.
   

▶dis[x][y] = dis[tmp[0]][tmp[1]] +1     #토마토가 익을 때 +1해서 날짜를 카운팅한다. 

 

▶dis[tmp[0]][tmp[1]]    board의 부모가 있는 좌표와 동일한 dis(체크리스트)의 좌표를 의미한다.