[BOJ] 7576. 토마토(python)

📌문제

💪아이디어

1. 안익은 토마토의 갯수 세기
   안익은 토마토가 0개면 0출력 후 프로그램종료
   

2. 익은 토마토 위치
   동시에 토마토들이 익기 시작하기 때문에 이미 익은 토마토들의 위치를 찾아서 시간을 세팅해야한다.
   

3. 모든 토마토가 익을 때까지 걸리는 시간 세기
   익은 토마토면 상하좌우검사해서

   • 안익은 토마토 익은 토마토로 상태바꾸기
   • 안익은 토마토 개수 -1
   • day+=1
   • queue넣기

bfs를 빠져나온 상태에서 더 익을 토마토가 있으면 -1출력하기

🥂코드

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

m,n = map(int,input().split())
ground=[]
unripe = 0
for _ in range(n):
    ground.append(list(map(int,input().split())))
    unripe += ground[-1].count(0)

if unripe == 0 : print(0)
else:
    dy = (-1,0,1,0)
    dx = (0,1,0,-1)
    queue = deque()

    for y in range(n):
        for x in range(m):
            if ground[y][x]==1:
                queue.append((0,y,x))

    while queue:
        day,ny,nx = queue.popleft()
        for i in range(4):
            ey,ex = ny+dy[i], nx+dx[i]
            if 0<=ey<n and 0<=ex<m:
                if ground[ey][ex]==0:
                    unripe -=1
                    if unripe == 0:
                        print(day+1)
                        exit(0)
                    ground[ey][ex]=1
                    queue.append((day+1,ey,ex))
    print(-1)