[Python_DFS&BFS] 백준 7576번 : 토마토

1. 문제

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

7576번: 토마토

 

 

 

2. 풀이 과정

import sys
from collections import deque

input = sys.stdin.readline

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

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


q = deque()
graph = []

for i in range(m):
  graph.append(list(map(int, input().split())))
  for j in range(n):
    if graph[i][j] == 1:
      q.append((i, j))

def bfs(graph):
  days = -1

  while q:
    days += 1
    for _ in range(len(q)):#for문 안에 append가 적용되기 전의 q길이가 반환됨
      x, y = q.popleft()
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0<=nx<m and 0<=ny<n and graph[nx][ny]==0:
          graph[nx][ny] = graph[x][y]+1
          q.append((nx, ny))

  for k in graph:#행을 하나씩 반환
    if 0 in k : return -1
  return days

print(bfs(graph))