1️⃣ 문제 설명

이전에 다나가 풀었던 7576번 토마토와 비슷하지만, 3차원으로 확장된 문제이다.

입출력 설명

층을 파악하기 쉽도록 층 단위로 초록색 박스를 표시했다.

입력

• 첫 번째 줄에는 가로, 세로, 높이를 뜻하는 M, N, H가 들어온다.
• 두 번재 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토 정보가 들어온다.
• 이러한 N개의 줄이 H번 반복하여 주어진다.

출력

• 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 출력한다.
• 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력한다.
• 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

2️⃣ 구현 아이디어

7576번 토마토 문제를 3차원으로 풀자

7576번 토마토 문제 풀이

1. 토마토 정보를 입력 받는다
2. 저장될 때부터 모든 토마토가 익어 있다면 0을 출력한다.
3. 그렇지 않다면 BFS를 돌면서 모든 토마토가 익는데 걸리는 최소 일수를 구한다.
4. 익지 않은 토마토가 있다면 -1을 출력한다.
5. 그렇지 않다면 최소 일수를 출력한다.

3️⃣ 코드 작성 - 틀렸습니다

import sys
from collections import deque

input = sys.stdin.readline

m, n, h = map(int, input().split()) # 가로, 세로, 높이
# 토마토 정보가 저장될 3차원 리스트
graph = [[[0 for _ in range(m)] for _ in range(n)] for _ in range(h)]
# 방문 여부를 저장하는 리스트
visited = [[[False for _ in range(m)] for _ in range(n)] for _ in range(h)]
d = deque([])
answer = 0

for i in range(h):
    for j in range(n):
        graph[i][j] = list(map(int, input().split()))

# 저장될 때부터 모든 토마토가 익어 있다면 True
flag = False
for list in graph:
    if all(0 not in elem for elem in list): # 한 층에 안 익은 토마토가 없다면
        flag = True

if flag:
    answer = 1
else:
    for i in range(h):
        for j in range(n):
            for k in range(m):
                if graph[i][j][k] == 1:
                    d.append((i, j, k))
                    visited[i][j][k] = True

    
    while d:
        cur = d.popleft()
        x, y, z = cur[1], cur[2], cur[0]
        dx = [-1, 0, 1, 0, 0, 0]
        dy = [0, -1, 0, 1, 0, 0]
        dz = [0, 0, 0, 0, 1, -1]

        for i in range(6):
            nx, ny, nz = x + dx[i], y + dy[i], z + dz[i]
            if nx < 0 or ny < 0 or nz < 0 or nx >= n or ny >= m or nz >= h or graph[nz][nx][ny] == -1 or visited[nz][nx][ny]:
                continue
            graph[nz][nx][ny] = graph[z][x][y] + 1
            visited[nz][nx][ny] = True
            d.append((nz, nx, ny))

# 0이 있는지 확인 > 있다면 안 익은 토마토가 있다는 의미
for list in graph:
    if not all(0 not in elem for elem in list): # 안 익은 토마토가 하나라도 있다면 False
        answer = 0
        break
    else:
        for elem in list:
            mx = max(elem)
            answer = max(answer, mx)

print(answer-1)

파이썬 내장 함수 all()

• iterable 내의 모든 요소가 참이거나 혹은 iterable 이 비어 있다면 True를 반환하고, 그 외의 경우에는 False를 반환하는 함수
• 안 익은 토마토가 있는지 확인할 때 사용하였다.

all([True, True, True, True, True]) # True
all([True, False, True, True, True]) # False

하지만 계속 62%쯤에서 틀렸습니다가 떴다 😞
결국 혼자 힘으로 이유를 찾지 못해 다른 사람들의 코드를 참고했다.
내 코드와 거의 비슷했지만, 나와 다르게 BFS 전에 저장될 때부터 모든 토마토가 익었는지 확인하는 부분이 없었다.
그래서 해당 부분을 지워서 다시 제출해보았고, 맞았습니다가 나왔다 !

4️⃣ 정답 코드

import sys
from collections import deque

input = sys.stdin.readline

m, n, h = map(int, input().split())
graph = [[[0 for _ in range(m)] for _ in range(n)] for _ in range(h)]
visited = [[[False for _ in range(m)] for _ in range(n)] for _ in range(h)]
d = deque([])
answer = 0

# i - 층, j - 행
for i in range(h):
    for j in range(n):
        graph[i][j] = list(map(int, input().split()))

for i in range(h):
    for j in range(n):
        for k in range(m):
            if graph[i][j][k] == 1: # 시작점들을 큐에 넣는다
                d.append((i, j, k))
                visited[i][j][k] = True

while d:
    cur = d.popleft()
    x, y, z = cur[1], cur[2], cur[0]
    dx = [-1, 0, 1, 0, 0, 0]
    dy = [0, -1, 0, 1, 0, 0]
    dz = [0, 0, 0, 0, 1, -1]

    for i in range(6):
        nx, ny, nz = x + dx[i], y + dy[i], z + dz[i]
        if nx < 0 or ny < 0 or nz < 0 or nx >= n or ny >= m or nz >= h or graph[nz][nx][ny] == -1 or visited[nz][nx][ny]:
            continue
        graph[nz][nx][ny] = graph[z][x][y] + 1
        visited[nz][nx][ny] = True
        d.append((nz, nx, ny))

# 0이 있는지 확인
for list in graph:
    if not all(0 not in elem for elem in list): # 안 익은 토마토가 하나라도 있다면 False
        answer = 0
        break
    else:
        for elem in list:
            mx = max(elem)
            answer = max(answer, mx)

print(answer-1)

5️⃣ 왜 BFS 전에 모든 토마토가 익었는지 확인하는 부분을 지워야 할까?

• 모든 토마토가 익었다면, BFS를 돌면서 원소가 갱신되지 않는다. 그러므로 graph의 원소의 최댓값을 출력해도 같은 결과가 나온다.
• 내가 적은 로직이 애초에 잘못되었다.
  • 알맞은 로직: 모든 층에 익은 토마토만 있어야 Flag가 True
  • 내가 작성한 로직: 한 층이라도 익지 않은 토마토가 있으면 Flag가 True