백준 7576번 토마토 (Python)

문제

인접한 곳에 놓여있는 토마토는 하루가 지나면 익는다. 이 때 모든 토마토가 익는데 몇일이나 소요되는가?

모든 토마토가 익을 수 없으면 -1을 출력한다.

(0: 안 익은 토마토, 1: 익은 토마토, -1: 없음.) 

풀이

간단히 bfs로 풀면된다.

python list에서 .pop(0) 실행시 첫번째 요소를 제거하고 두번째 요소를 첫번째로, 세번째 요소를 두번째로... 이동하는 작업을 하기때문에 시간이 O(N)만큼 소요된다고한다. collections 라이브러리의 queue 모듈을 사용하자.

import sys
import collections
 
input = sys.stdin.readline
 
M, N = map(int, input().split())
 
unriped = 0
 
farm = []
tomato = collections.deque([])
 
for i in range(N) :
 
    farm.append(list(map(int, input().split())))
 
    for t in range(M) :
        if farm[i][t] == 1 :
            tomato.append((i, t))
        elif farm[i][t] == 0 :
            unriped += 1
 
days = 1
 
while tomato :
 
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    t = tomato.popleft()
 
    x = t[0]
    y = t[1]
 
    for i in range(4) :
 
        nx = x + dx[i]
        ny = y + dy[i]
 
        if nx >= N or nx < 0 or ny >= M or ny < 0 :
            continue
        if farm[nx][ny] != 0:
            continue
 
        farm[nx][ny] = farm[x][y] + 1
        tomato.append((nx, ny))
        days = max(farm[nx][ny], days)
        unriped -= 1
 
if unriped == 0 :
    print(days-1)
else :
    print(-1)

문제 출처 : https://www.acmicpc.net/problem/7576