#221 백준 파이썬 [7576] 토마토 - BFS

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

 

Solution

BFS로 구현할 수 있다.

queue로 구햔하면 시간초과가 뜨기에 deque로 구현해준다. BFS로 해야, 1에서 최근접값을 찾을 수 있다.

 

1) 먼저 이미 익은 토마토를 queue에 넣고

2) queue안의 토마토를 앞에서부터 뽑아내준다.

3) 뽑아낸 토마토의 상하좌우에 안익은 토마토가 있으면 현재까지의 토마토 날에 +1을 해준다.

4) while문이 모두 돈 뒤, 0이 있으면 -1을 출력해주고, 없다면 배열 내의 최댓값 -1 을 출력해준다.

 

Python Code

import copy
from collections import deque


M, N = map(int, input().split())
box = []
for _ in range(N):
    box.append(list(map(int, input().split())))
ripen_box = copy.deepcopy(box) #같은 리스트를 하나 더 생성(안해도 상관 없음)

queue = deque() #일반 리스트로 큐를 구현하면 시간이 너무 오래걸린다
for i in range(N):
    for j in range(M):
        if box[i][j] == 1:
            queue.append([i, j]) #이미 익어있는 토마토 위치를 큐에 넣어줌
    
while queue:
    [i, j] = queue.popleft() #하나씩 빼면서 비교
    
    #위
    if i > 0 and ripen_box[i-1][j] == 0:
        queue.append([i-1, j]) #큐에 넣고
        ripen_box[i-1][j] = ripen_box[i][j] + 1 #하루 더 기다려야하니, 1을 더해준다.
        
    #아래
    if i < N-1 and ripen_box[i+1][j] == 0:
        queue.append([i+1, j])
        ripen_box[i+1][j] = ripen_box[i][j] + 1
    
    #왼쪽
    if j > 0 and ripen_box[i][j-1] == 0:
        queue.append([i, j-1])
        ripen_box[i][j-1] = ripen_box[i][j] + 1
    
    #오른쪽
    if j < M-1 and ripen_box[i][j+1] == 0:
        queue.append([i, j+1])
        ripen_box[i][j+1] = ripen_box[i][j] + 1
        
answer = True
for row in ripen_box: #0이 하나라도 있을 경우 -1출력
    if 0 in row:
        print(-1)
        answer = False
        break
        
if answer:
    min_day = 0
    for row in ripen_box:
        min_day = max(min_day, max(row)) #익기 위한 최소 날 = ripen_box의 최댓값
    print(min_day-1)