[백준 7569] 토마토 (python)

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

7569번: 토마토

토마토 문제

상자안에 놓여있는 토마토가 옆으로 갈수록 익어가는데, 전체 토마토가 익는데 걸리는 최소 일 수를 찾는 문제이나, 2차원이 아닌 3차원으로 고려해줘야하는 문제

BFS를 활용하여 풀고, 3차원 리스트로 만들어주면 간단하게 해결 할 수 있는 문제

내가 푼 정답코드

def ripe(): # 3차원 리스트의 BFS
    while queue:
        z, y, x = queue.popleft()
        for dz, dy, dx in spread:
            nz, ny, nx = z + dz, y + dy, x + dx
            if 0 <= nz < H and 0 <= ny < N and 0 <= nx < M and tomato[nz][ny][nx] == 0:
                tomato[nz][ny][nx] = tomato[z][y][x] + 1
                queue.append([nz, ny, nx])

import sys
from collections import deque
M, N, H = map(int, sys.stdin.readline().split())
tomato =[[list(map(int, sys.stdin.readline().split())) for _ in range(N)] for _ in range(H)]
spread = [[1,0,0],[-1,0,0],[0,1,0],[0,-1,0],[0,0,1],[0,0,-1]]
queue = deque()
num = out = 0

for i in range(H):
    for j in range(N):
        for k in range(M):
            if tomato[i][j][k] == 1:
                queue.append([i,j,k]) # 시작 지점을 queue에 삽입
ripe()

for i in range(H):
    for j in range(N):
        for k in range(M):
            if tomato[i][j][k] == 0: #만약 0인게 남아있으면
                out = 1 # out에 1저장
            if num < tomato[i][j][k]: #3차원 배열의 최대값 구하기
                num = tomato[i][j][k]
if out == 0 :
    print(num-1)
else :
    print(-1)

미로 탐색할때 걸리는 최소 거리를 구하는 문제와 동일한 형태의 문제이다.

다만 3차원 형태로 이루어진 구조이고, 2차원과 다르게 위와 아래 구조 형태이면서 중간에 토마토가 1개가 아니라 여러 개로부터 퍼지는 경우도 고려를 해줘야하는데, 이건 그냥 처음에 queue에 넣고 시작하면 queue에 선입선출 구조에 의해 자연스레 여러 개로부터 퍼지는 경우수도 고려해준다.

미로 거리 찾기 문제를 풀어봤고, queue의 구조를 잘 이해하고 있으면서 리스트를 활용할줄 안다면(3차원) 쉽게 풀 수 있는 문제

---

느낀 점

3차원 리스트를 활용하는 문제는 처음 접해봤다. 항상 많이써야 2차원 리스트였는데, 3차원으로 넘어가니 처음엔 헷갈렸으나, 결국 2차원과 다를게 없는 방식으로 풀면 된다 생각하고 접근했더니 쉽게 해결 할 수 있던 문제

3차원 리스트를 써볼 기회가 생겨서 나름 신기했다!