7576 - 토마토 (파이썬/python)

문제 링크 : https://www.acmicpc.net/problem/7576

풀이

BFS문제

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

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

queue = deque()

matrix = []
# visit 그래프에는 각 칸의 토마토가 익는데 걸리는 시간을 표시
visit = [[-1]*m for _ in range(n)]

for i in range(n) :
  new = list(map(int, input().split()))
  matrix.append(new)
  for j in range(m) :
  	# 익은 토마토가 있을 경우 queue에 추가해 bfs 탐색의 출발점으로 입력
    if new[j] == 1 :
      queue.append([i,j])
      visit[i][j] = 0

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

def bfs(queue) :
  if len(queue) == 0 :
    return -1

  while queue :
    y, x = queue.popleft()

    for i in range(4) :
      ny = y + dy[i]
      nx = x + dx[i]
      if nx < 0 or nx >= m or ny <0 or ny >= n :
        continue
      if matrix[ny][nx] == 0 and visit[ny][nx] == -1 :
        queue.append([ny,nx])
        visit[ny][nx] = visit[y][x] + 1

  # 모든 칸을 돌면서 토마토가 있지만 접근하지 못한 칸이 있는지 체크
  # 가장 오래 걸린 시간도 체크
  days = 0
  for i in range(n) :
    for j in range(m) :
      if matrix[i][j] == 0 and visit[i][j] == -1 :
        return -1
      if matrix[i][j] == 0 and visit[i][j] > -1 :
        days = max(days,visit[i][j])
  return days

print(bfs(queue))