[boj] 백준 7569 토마토 python 풀이

감자156 2023. 6. 16. 23:33

문제

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

7569번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,

www.acmicpc.net

문제 풀이

bfs 문제로, 다음 이동할 위치를 위아래 3차원까지 고려해주면 된다. 답 분기가 많아서 헷갈렸음

코드

import sys
input = sys.stdin.readline
import collections


M, N, H = map(int,input().split())
q = collections.deque()

tomato_tower = []

to_ripe = 0
for i in range(H):
    tmp2 = []
    for j in range(N):
        tmp = list(map(int,input().split()))
        for k in range(M):
            if tmp[k] == 1:
                q.append((i,j,k))
            elif tmp[k] == 0:
                to_ripe += 1
        tmp2.append(tmp)
    tomato_tower.append(tmp2)
  
move = {(-1,0,0), (1,0,0), (0,-1,0), (0,1,0), (0,0,-1), (0,0,1)}
day = 0
while q:
    z,x,y = q.popleft()
    
    for tz, tx, ty in move:
        nz = tz + z
        ny = ty + y
        nx = tx + x

        if 0<=nx<N and 0<=ny<M and 0<=nz<H and tomato_tower[nz][nx][ny] == 0:
            tomato_tower[nz][nx][ny] = tomato_tower[z][x][y] + 1
            q.append((nz,nx,ny))

            to_ripe -= 1
            day = max(day, tomato_tower[nz][nx][ny])
            if to_ripe == 0:
                print(day-1)
                exit()

if to_ripe == 0: # 처음부터 다 익어있는 경우
    print(to_ripe)
    exit()
if to_ripe>0: # 못익히는 경우
    print(-1)
    exit()
print(day-1) # 다 익음