[백준 7576번] 토마토 (Python/파이썬)

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

7576번: 토마토

백준 2178번과 거의 똑같은 문제라고 할 수 있다.

2178번에서 미로를 탐색할때 몇번만에 갈 수 있는지 깊이 지도를 그려서 문제를 해결했었다.

이번 문제도 마찬가지로 어차피 하루당 한 칸씩 토마토가 익으므로 깊이지도를 그리면된다.

미로 문제와 다른점은 미로는 BFS의 출발점이 하나였지만, 토마토는 시작할 때 부터 여러개가 익어 있을 수 있기 때문에 queue에 익은 토마토를 모두 넣고 시작해야한다. 

이번에는 깊이지도를 따로 만들지 않고 토마토 상자의 숫자를 깊이로 생각하여 풀었다.

위의 점을 제외하면 미로문제와 다른게 하나도 없으므로 자세한 설명은 생략하고, 코드는 다음과 같다.

 

import sys
from collections import deque
input = sys.stdin.readline
M, N = map(int, input().split())
queue = deque([])
tomato = []
## 토마토 상자 만들기
for _ in range(N):
  tomato.append(list(map(int, input().split())))

## 익은 토마토는 모두 queue에 넣어놓기
for i in range(N):
  for j in range(M):
    if tomato[i][j] == 1:
      queue.append((i,j))

## 위, 아래, 오른쪽, 왼쪽을 탐색하기 위한 임시 리스트
dx = [0,1,0,-1]
dy = [1,0,-1,0]

## BFS를 하면서 좌표가 상자 크기안에 있고, 익지 않은 토마토라면 전에 익은 토마토의 일수+1을 넣어준다.(깊이지도 만들기)
def BFS():
  while queue:
    (a, b) = queue.popleft()
    for i in range(4):
      temp_a = a + dx[i]
      temp_b = b + dy[i]
      if temp_a >= 0 and temp_b >= 0 and temp_a <= N-1 and temp_b <= M-1:
        if tomato[temp_a][temp_b] == 0:
          queue.append((temp_a,temp_b))
          tomato[temp_a][temp_b] = tomato[a][b] + 1

BFS()
day = 1
## 익지 않은 토마토가 있으면 프로그램 종료
for i in range(N):
  for j in range(M):
    if tomato[i][j] == 0:
      print(-1)
      sys.exit()
    temp = tomato[i][j]
    day = max(day, temp)
print(day-1)

 

 

 

글이나 코드에 대한 조언 모두 환영합니다.