[백준 파이썬] 7569 토마토

📌문제 출처

백준 단계별 문제풀이 - 그래프와 순회
https://www.acmicpc.net/problem/7569

7569번: 토마토

❓ 문제

 

❗ 풀이

• 3차원 bfs 활용

📗 풀이 코드

import sys
from collections import deque
input = sys.stdin.readline

def bfs() : # 0일자부터 토마토 익히기 시작
    global not_good
    cur_day = 0 # 현재 날짜
    while stack :
        z,y,x,chk_day = stack.popleft()
        if cur_day != chk_day : # 날짜가 넘어갔다면
            if not not_good : # 전부 익었다면
                return chk_day # 전부 익은 날짜 반환
            cur_day += 1 # 현재 날짜 하루 더 진행
        chk_day += 1 # 확인할 날짜 하루 더 진행
        if (0<z) and (not tomatoes[z-1][y][x]):
            tomatoes[z-1][y][x] = 1
            stack.append([z-1,y,x,chk_day])
            not_good -= 1
        if (z<(h-1)) and (not tomatoes[z+1][y][x]) :
            tomatoes[z+1][y][x] = 1
            stack.append([z+1,y,x,chk_day])
            not_good -= 1
        if (0<y) and (not tomatoes[z][y-1][x]) :
            tomatoes[z][y-1][x] = 1
            stack.append([z,y-1,x,chk_day])
            not_good -= 1
        if (y<(n-1)) and (not tomatoes[z][y+1][x]) :
            tomatoes[z][y+1][x] = 1
            stack.append([z,y+1,x,chk_day])
            not_good -= 1
        if (0<x) and (not tomatoes[z][y][x-1]) :
            tomatoes[z][y][x-1] = 1
            stack.append([z,y,x-1,chk_day])
            not_good -= 1
        if (x<(m-1)) and (not tomatoes[z][y][x+1]) :
            tomatoes[z][y][x+1] = 1
            stack.append([z,y,x+1,chk_day])
            not_good -= 1
    return -1

m,n,h = map(int,input().split())
not_good = 0 # 안 익은 개수
stack = deque([]) # bfs 넣을 stack
tomatoes = [] # 전체 상자
for z in range(h): # 층(z) 반복
    floor = []
    for y in range(n): # 행(y) 반복
        row = list(map(int,input().split()))
        for x,tom in enumerate(row): # 열(x) 반복
            if tom == 1: # 익었다면
                stack.append([z,y,x,0]) # bfs에 먼저 넣어두기, 0은 일자
            elif tom == 0 : # 안 익었다면
                not_good += 1 # 안 익은 개수 추가
        floor.append(row) # 층에 행 넣기
    tomatoes.append(floor) # 전체 상자에 층 넣기
dx,dy,dz = [0,0,-1,1,0,0],[-1,1,0,0,0,0],[0,0,0,0,-1,1] # 상하좌우위아래 방향
if not not_good : # 애초에 안익은 토마토가 없다면
    print(0)
else :
    print(bfs())

📗 코드 해설

• 7576 토마토(https://nembizzang.tistory.com/158)의 3차원 확장 문제이다.
• n행 m열의 상자가 h층 쌓여있으므로 삼중 for문을 통해 입력값을 받아준다.
  이때 안 익은 토마토의 개수를 세어주고, 익은 토마토의 위치를 세어준다.
• 2차원 bfs문제에선 상하좌우로 이동하며 토마토를 익혔지만 3차원에선 위아래 두가지 방향을 추가해준다.
• 그리고 bfs 함수 내에서 익은 토마토의 위치를 시작으로 토마토의 위치, 현재 날짜를 stack에 넣어서 반복시켜준다.
• 같은 위치, 같은 날짜에서 익힐 수 있는 모든 토마토의 위치와 다음 날짜가 stack에 연속적으로 들어간다.
• 따라서 stack에서 해당 날짜를 보았을 때 현재 날짜와 다르다면 그 때는 하루가 지난 날짜이다.
• 그 시점에서 익은 토마토의 개수를 확인하고 0이라면 bfs를 멈춘다.
• 아니라면 현재 날짜를 하나 더 해주고 bfs를 반복한다.
• 이 때 for 문으로 상하좌우위아래를 반복시켜주는 것보다 여섯번의 if 문으로 상하좌우위아래를 결정하는 것이
  if 조건문을 확인하는 시도가 적으므로 if문으로 bfs를 진행한다.