[ BOJ 7576 ] 토마토 (Python)

문제

https://www.acmicpc.net/problem/7576

토마토가 '상하좌우' 에 영향을 받는다.
그래프를 만들때 딕셔너리가 아닌 이중배열을 사용해보았다.

문제 풀이

1. 익은 토마토이면 (x,y,cnt)를 queue에 넣어주었다.
2. 익은 토마토의 상하좌우가 안익은 토마토이면, 익었다고 체크해준 뒤에 (nx,ny,cnt+1)를 queue에 넣어준다.
3. cnt를 따로 day라는 전역변수에 담아서, 일수를 저장해준다.
4. 배열을 전체 검사하면서 안익은 토마토가 있으면 -1을 리턴해주고, 없으면 day를 리턴한다.

코드

import sys
from collections import deque

input = sys.stdin.readline

m,n = map(int,input().rstrip().rsplit())
done_tomato = deque([])
matrix = [[0] * m for _ in range(n)]
day = 0

dx = [-1, 1, 0, 0]  #상, 하, 좌, 우
dy = [0, 0, -1, 1]

for i in range(n):
    row = input().rstrip().rsplit()
    for j,num in enumerate(row):
        matrix[i][j] = num

for row in range(n):
    for col in range(m):
        if matrix[row][col]=='1':
            done_tomato.append((row,col,0))

while done_tomato:
    row, col, cnt = done_tomato.popleft()
    for k in range(4):
        nx = row + dx[k]
        ny = col + dy[k]
        if 0 <= nx < n and 0 <= ny < m:
            if matrix[nx][ny] == '0':
                matrix[nx][ny] = '1'
                done_tomato.append((nx,ny,cnt+1))
                day = cnt + 1

def check(day):
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == '0':
                return -1
    return day

print(check(day))