[ BOJ / 파이썬 ] 7576 토마토

BFS 

& 시작점이 여러 개인 경우

 

deque를 사용하고, 각 토마토에 해당 날짜를 붙여서 같이 묶어줬다. 

 

1차 제출 . 통과

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

def is_all_ripped(board):
  for i in range(len(board)):
    for j in range(len(board[0])):
      if board[i][j] == 0:
        return False
  return True

def main():
  m, n = map(int, input().split())
  board = []
  tomato = deque([])
  for i in range(n):
    row = list(map(int, input().split()))
    for j in range(len(row)):
      if row[j] == 1:
        tomato.append((0, i, j))
    board.append(row)
    
  current_day = 0

  #정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]
  while tomato:
    day, x, y = tomato.popleft()
    if current_day != day:
      current_day += 1
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 0:
        board[nx][ny] = 1
        tomato.append((day+1, nx, ny))

  #토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다.
  if is_all_ripped(board):
    print(current_day)
  else:
    print(-1)
if __name__ == '__main__':
  main()

 

 

마찬가지로 5개월 전 풀었던 문제인데, 이번에는 훨씬 수월하게 풀 수 있었다. 그리고 시간복잡도도 절반으로 줄었다. 

 

지난 풀이 ( 링크 )