[1] 토마토

[robert-min]

문제 추천 이유!!

• 3차원 BFS 완전 탐색문제
• BFS를 이해하면 어렵지 않지만 코드를 작성하는데 시간이 걸리는 문제로 풀어보면 한 번 풀어보면 좋을 듯

문제 링크

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

*작성가이드 입니다.

1. 작성자가 먼저 문제를 풀어봅니다.
2. 문제를 풀고나서 난이도를 설정합니다.
   • 1 : 30분 이내로 손 쉽게 풀 수 있음
   • 2 : 1시간 이내로 고민하면 풀 수 있음
   • 3 : 1시간 이상 걸리거나 어려움
3. Coding test Basic template을 사용하여 이슈를 생성합니다.
   • 제목은 : [난이도] 문제명으로 작성합니다.
   • 내용은 : 문제 링크만 추가하세요
   • 문제 사이트를 label로 추가해주세요. 기본값은 백준
4. 문제 풀이는 이슈의 코멘트로 추가해주세요
   • 풀이에 걸린 시간, 풀이 유형, 방식은 간단하게
   • 문제를 풀고나서 스스로 풀이 또는 오답노트를 정리하는 느낌으로!!
5. 다른 사람에게 채팅으로 직접 문제를 추천하세요.
   • 디스코드 채널을 통해 다른 모임원에게 문제를 추천
   • 해당 모임원은 문제를 풀고 코멘트를 통해 추가로 공유하기!!

---

아래는 comment 템플릿입니다.(복사해서 사용)

⏰ 소요 시간 : 
🗂️ 유형 :

🖌️ 문제 풀이
- 

[robert-min]

⏰ 소요 시간 : 20분 🗂️ 유형 : BFS - 3차원

🖌️ 문제 풀이

• 인풋값 입력 시 3차원 처리를 고려해서 작업
• Return : 익지 않은 사과의 수(cnt)를 기준으로 일수(day)

"""
Return : 토마토가 익는 최소 일수
- 1일 => 상하좌우, 위아래 익음

- 3차원 BFS 탐색
"""
import sys
from collections import deque

dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]

def bfs(start):
    global cnt, day
    while start:
        Q = deque(start)
        day += 1
        start = []
        while Q:
            x, y, z = Q.popleft()
            for k in range(6):
                nx = x + dx[k]
                ny = y + dy[k]
                nz = z + dz[k]
                if nx < 0 or nx >= N: continue
                if ny < 0 or ny >= M: continue
                if nz < 0 or nz >= H: continue

                if matrix[nz][nx][ny] == 0:
                    cnt -= 1
                    matrix[nz][nx][ny] = 1
                    start.append((nx, ny, nz))

if __name__ == "__main__":
    input = sys.stdin.readline
    M, N, H = map(int, input().split())

    matrix = []
    start = []
    cnt = 0
    day = -1
    for k in range(H):
        temp = []
        for i in range(N):
            row = list(map(int, input().split()))
            for j, val in enumerate(row):
                if val == 1:
                    start.append((i, j, k))
                elif val == 0:
                    cnt += 1
            temp.append(row)
        matrix.append(temp)

    if cnt == 0:    # 익지 않은 사과가 없을 경우 => 0(탐색할 필요X)
        print(0)
    else:
        bfs(start)  # 탐색
        if cnt == 0:    # 탐색 후 모든 사과가 익은 경우 => day
            print(day)
        else:
            print(-1)   # 탐색 후 익지 않은 사과가 있는 경우 => -1