7576번 – 토마토

7

문제

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

풀이

코드

from collections import deque
from copy import deepcopy

m, n = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
board = [[-1]*m] + board + [[-1]*m]
for y in range(len(board)): board[y] = [-1] + board[y] + [-1]
dyx = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def answer():
  global m, n, board
  day = BFS()
  # 다 익었어야 했는데, 안익었다면...
  if 토마토가다익었나(board) is False: return -1
  return day

def 익은토마토찾기(board):
  좌표들 = []
  for y in range(len(board)):
    for x in range(len(board[y])):
      if board[y][x] == 1: 좌표들.append((y, x))
  return 좌표들

def 토마토가다익었나(board):
  for y in range(len(board)):
    for x in range(len(board[y])):
      if board[y][x] == 0: return False
  return True

def BFS():
  global board
  Q = deque(익은토마토찾기(board))
  NQ = deque()
  day = 0
  while(len(Q) > 0):
    y, x = Q.popleft()
    for dy, dx in dyx:
      ny, nx = dy+y, dx+x
      if board[ny][nx] == 0:
        board[ny][nx] = 1
        NQ.append((ny, nx))
    if len(Q) == 0:      
      if len(NQ) > 0:
        Q = deepcopy(NQ)
        NQ = deque()
        day += 1
      else: break
  return day

print(answer())

Add Comment