백준 7576: 토마토 해설- python

✏️ 문제

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

7576번: 토마토

 

✏️ 풀이

BFS로 풀이한다.

from collections import deque

m,n=map(int,input().split())
#토마토를 받아서 넣기
matrix=[list(map(int, input().split())) for _ in range(n)]

queue=deque([])
#이동표현
dx,dy=[-1,1,0,0],[0,0,-1,1]
#정답을 담을 변수
res=0

#queue에 처음에 받은 토마토의 위치좌표를 담는다
for i in range(n):
  for j in range(m):
    if matrix[i][j]==1:
      queue.append([i,j])

def bfs():
  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx,ny=dx[i]+x, dy[i]+y
      #해당좌표가 좌표범위를 넘지않고 그 좌표에 안익은 토마토가 있어야한다.
      if 0<=nx<n and 0<=ny<m and matrix[nx][ny]==0:
        #익히고 1을 더하면서 횟수세기
        matrix[nx][ny]=matrix[x][y]+1
        queue.append([nx,ny])

bfs()
for i in matrix:
  for j in i:
    #안익은 토마토가 있으면 -1출력
    if j==0:
      print(-1)
      exit(0)
  #다익힌경우 최댓값이 정답
  res=max(res,max(i))
print(res-1)