7576번 - 토마토(Python

 

풀이

최소 일수를 구해야 하므로, bfs를 이용하여 문제를 해결한다.

 

모든 익은 토마토의 좌표를 큐에 넣은 후, bfs를 실행하며 연결되어 있는 모든 토마토가 익을 때까지의 일수를 센다.

bfs가 끝난 후, 아직 안 익은 토마토가 있다면 모두 익는 것이 불가능 한 것이므로 -1을 출력한다.

모두 익었다면 계산한 ans를 출력한다.

(ans는 -1부터 시작해야 오늘로부터 지나는 일수가 된다.)

코드

from collections import deque
import sys


input = sys.stdin.readline

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
ans = -1
q = deque()

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

if len(q) == 0:
    print(-1)
else:
    while q:
        ans += 1
        for el in range(len(q)):
            node = q.popleft()
            y, x = node[0], node[1]
            for a in range(4):
                ny = y + dy[a]
                nx = x + dx[a]
                if 0 <= ny < N and 0 <= nx < M and tomatoes[ny][nx] == 0:
                    tomatoes[ny][nx] = 1
                    q.append([ny, nx])

    for i in range(N):
        for j in range(M):
            if tomatoes[i][j] == 0:
                print(-1)
                sys.exit(0)
    print(ans)