BOJ 7576. 토마토 (Python)

문제

BOJ 7576

내가 생각한 풀이

2중 for문을 돌며 익은 토마토가 있는 좌표를 queue에 넣어둔다.

dist 배열을 두고 2중 for문을 돌 때 익은 토마토들이 있는 좌표의 값을 0으로 초기화시킨다.

 

BFS를 수행하며 익을 수 있는 토마토들을 다 익게 만든다.

dist 배열의 해당 좌표 값은 이전 값 + 1로 초기화시킨다.

 

2중 for문을 돌며 익지 않은 토마토가 있으면 -1을 출력하고 실행을 종료한다. (익지 않은 토마토는 dist 배열의 값이 -1이면서 graph의 값이 0인 좌표이다.)

모두 익을 때까지의 날짜를 저장할 변수 mx를 선언하고 dist[i][j]와 값을 비교해가며 더 큰 수를 저장한다.

모두 익어있다면 mx를 출력한다.

 

코드 (Python)

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

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

direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
queue = deque([])
dist = [[-1] * M for _ in range(N)]
for i in range(N):
    for j in range(M):
        if graph[i][j] == 1:
            queue.append((i, j))
            dist[i][j] = 0

while queue:
    xp, yp = queue.popleft()
    for dx, dy in direction:
        nx, ny = xp + dx, yp + dy
        if not (0 <= nx < N and 0 <= ny < M):
            continue
        if dist[nx][ny] == -1 and graph[nx][ny] == 0:
            queue.append((nx, ny))
            dist[nx][ny] = dist[xp][yp] + 1

mx = 0
for i in range(N):
    for j in range(M):
        if dist[i][j] == -1 and graph[i][j] == 0:
            print(-1)
            exit(0)
        mx = max(mx, dist[i][j])
print(mx)