백준 7576 토마토 (Python)

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

7576번: 토마토

우선 한 단계씩 퍼져나가야 하기 때문에 BFS를 사용했다.

 

우선 익은 토마토들의 위치를 가져와야 하기 때문에 반복문을 사용하여 1인 토마토의 위치를 가져온다.

여기서 처음에는 리스트를 사용했었는 데, 시간 초과가 발생한다.

deque를 사용하는 것을 추천한다.

 

익은 토마토들을 저장할 때 ripe이라는 deque를 사용했는 데, 여기에는 익은 토마토의 위치 뿐만 아니라 지난 날짜까지 저장을 해준다.

이렇게 현재 날짜를 저장해주어야 다음 차례에 날짜를 +1해가며 BFS를 진행할 수 있기 때문이다.

 

익은 토마토로 부터 4방향을 탐색하고 안 익은 토마토가 있다면, 해당 토마토에 날짜 +1 한 정보와 위치를 ripe deque에 추가해준다.

그리고는 ripe가 남아 있을 동안 반복문을 진행하고 만약 while로 모든 ripe를 탐색한 후에도 0인 토마토가 남아있다면 -1을 출력하며, 아니라면 가지고 있던 max_result를 출력해준다.

 

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

tomato = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

ripe = deque()

for m in range(M):
    for n in range(N):
        if tomato[m][n] == 1:
            ripe.append([0, m, n])

max_result = 0

while ripe:

    cur_cnt, cur_m, cur_n = ripe.popleft()

    max_result = max(max_result, cur_cnt)

    for next_m, next_n in [[cur_m, cur_n + 1], [cur_m, cur_n - 1], [cur_m + 1, cur_n], [cur_m - 1, cur_n]]:
        if 0 <= next_m < M and 0 <= next_n < N and tomato[next_m][next_n] == 0:
            tomato[next_m][next_n] = 1
            ripe.append([cur_cnt + 1, next_m, next_n])


is_finish = True

for m in range(M):
    for n in range(N):
        if tomato[m][n] == 0:
            is_finish = False
            break
    if not is_finish:
        break

print(max_result if is_finish else -1)