백준 7576번: 토마토(Python)

문제

백준 7576번: 토마토

풀이

bfs로 해결했다

소스코드

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

ripetmt, notyet, empty = 1, 0, -1     #익은 토마토, 익지않은 토마토, 비어있음
dir = [(-1, 0),(1, 0),(0, -1),(0, 1)] #상하좌우

def bfs():
    ans = 0

    while len(ripe)>0:
        o = ripe.popleft()
        r, c, day = o[0], o[1], o[2]
        for d in dir:
            nextr, nextc = r+d[0], c+d[1]
            if nextr<0 or nextr>=N or nextc<0 or nextc>=M:
                #상자 범위 초과
                continue
            nextb = box[nextr][nextc]
            if nextb==empty or nextb==ripetmt:
                #비어있거나 이미 익은 상태
                continue
            else:
                # 익지 않은 토마토
                # 익은 상태로 바꾼 후에 큐에 넣어준다
                box[nextr][nextc] = ripetmt
                ans = max(ans, day+1)
                ripe.append((nextr, nextc, day+1))  

    for i in range(N):
        for j in range(M):
            # 상자에 익지 않은 토마토가 있는지 검사
            if box[i][j]==notyet:
                ans = -1
                break
    return ans


M, N = map(int, input().rstrip().split())
box = [list(map(int, input().rstrip().split())) for _ in range(N)]

ripe = deque()
for i in range(N):
    for j in range(M):
        if box[i][j]==ripetmt:
            ripe.append((i, j, 0))

print(bfs())