[백준 7576번] 토마토 -python

문제 링크

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

7576번: 토마토

풀이 

- bfs 문제 

- 토마토의 위치 값을 미리 큐에 삽입해준 후 bfs를 실행하고 

0이 아직도 존재한다면 -1 출력 

0이 없다면 익는데 가장 오래 걸리는 토마토 값 출력. 이 때 시작 값을 1로 시작했으므로 1을 빼준다. 

from collections import deque 

INF = int(1e9)
dx = [ 1, -1, 0, 0 ]
dy = [ 0, 0, 1, -1 ]

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))

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()
result = 0

for i in range(n):
  # 익지 않은 토마토가 존재한다면 
  if 0 in graph[i]:
    print(-1)
    break
  # 가장 오래 걸리는 토마토 값 구하기   
  else:
    result = max(result,max(graph[i]))

  if i == n-1:
    print(result-1)