[Boj] 토마토 7576(python)

문제링크 : https://www.acmicpc.net/problem/7576

구해야 할 목적이 토마토가 익는데 최소한의 시간이므로, BFS를 선택함

토마토가 있는 좌표를 deque로 관리하여 큐로 관리

BFS 함수를 실행하여 좌표를 하나씩 꺼내서 상하좌우 검사 후 조건에 맞는 좌표를 큐에 넣음

이때 다음 좌표의 값은 현재 좌표의 값 + 1로 하면 쉽게 구할 수 있음

이 경우 실제 시간보다 1이 더 크므로 최종적으로 matrix를 검사하면서 0이 있는 경우와 아닌 경우를 고려해서 출력하면 끝

import sys
from collections import deque
sys.setrecursionlimit(10**8)

def BFS():
    while tomatos:
        current_row, current_col = tomatos.popleft()
        for i in range(4):
            next_row, next_col = current_row + dx[i], current_col + dy[i]
            if 0 <= next_row < row and 0 <= next_col < col and matrix[next_row][next_col] == 0:
                matrix[next_row][next_col] = matrix[current_row][current_col] + 1
                tomatos.append([next_row, next_col])


col, row = map(int, input().split())
matrix = []
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
for _ in range(row):
    tmp = list(map(int, input().split()))
    matrix.append(tmp)

tomatos = deque()
for i in range(row):
    for j in range(col):
        if matrix[i][j] == 1:
            tomatos.append([i, j])

BFS()
answer = 1
for i in range(row):
    for j in range(col):
        if answer < matrix[i][j]:
            answer = matrix[i][j]
        if matrix[i][j] == 0:
            answer = 0
            break
    if answer == 0:
        break
print(answer-1)