[Algorithm🧬] 백준 7576 : 토마토

문제

import sys
from collections import deque


def BFS():
    moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상 하 좌 우 에 영향.

    count = 0

    q = deque()

    for i in range(N):
        for j in range(M):
            if tomatoes[i][j] == 1:
                q.append((i, j, 1))
            elif tomatoes[i][j] == 0:
                count += 1

    if count == 0:
        return 0


    while q:
        r, c, day = q.popleft()

        for x, y in moves:
            tr, tc, tday = r + x, c + y, day + 1

            if not 0 <= tr < N:
                continue
            if not 0 <= tc < M:
                continue

            if tomatoes[tr][tc] != 0:
                continue

            q.append((tr, tc, tday))
            tomatoes[tr][tc] = tday
            count -= 1

            # 여기서 거를것.
            if count == 0:
                return day


    return -1


# 행 N 열 M
M, N = map(int, sys.stdin.readline().split())
# 1 익은 토마토 0 안 익은 토마토 -1 토마토 없음.
tomatoes = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

check = [[0] * M] * N


print(BFS())

count 를 이용해서 while q 의 종료 조건을 준다는 생각까지는 했는데,
count 를 for 문 안쪽에서 안했더니 바로 거를 수 없는 케이스들이 생겨버렸다.