[백준] 7569번: 토마토(3차원) 파이썬

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

토마토 농담곰

 

유명한 토마토 문제

근데 3차원인.

 

첫째 줄에 상자의 크기를 나타내는 M, N, H가 주어지고 각 줄마다 상자에 들어있는 토마토 상태가 주어짐:

• 1: 익은 토마토
• 0: 익지 않은 토마토
• -1: 토마토가 들어있지 않은 칸

우리가 해야 할 일은 모든 토마토가 다 익을 때까지 며칠이 걸리는지 구하는 거임. 만약 처음부터 모든 토마토가 다 익어있으면 0을 출력하고, 토마토가 다 익지 못하면 -1을 출력하면 됨.  

 

풀이

 

import sys
from collections import deque

# 방향 벡터 (상, 하, 좌, 우, 위, 아래)
dx = [1, 0, -1, 0, 0, 0]
dy =[0, 1, 0, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]

m, n, h = map(int, sys.stdin.readline().split())
arrs = []
for _ in range(h):
  arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
  arrs.append(arr)
q = deque()
for z in range(h):
  for y in range(n):
    for x in range(m):
      if arrs[z][y][x] == 1:
        q.append((z, y, x))

def bfs():
  while q:
    z, y, x = q.popleft()
    for i in range(6):
      nx = x + dx[i]
      ny = y + dy[i]
      nz = z + dz[i]
      if 0 <= nx < m and 0 <= ny < n and 0 <= nz <h:
        if arrs[nz][ny][nx] == 0:
          arrs[nz][ny][nx] =  arrs[z][y][x] + 1
          q.append((nz,ny,nx))

bfs()
max_day = 0
for x in range(m):
  for y in range(n):
    for z in range(h):
      if arrs[z][y][x] == 0:
        print(-1)
        exit(0)
      max_day = max(max_day, arrs[z][y][x])

print(max_day-1)

 

코드 해설

1. 방향 벡터 설정:
   •  상, 하, 좌, 우, 위, 아래를 나타내는 방향 벡터를 설정. 이걸 통해서 bfs 탐색을 한다.
2. 입력 받기:
   •  M, N, H를 입력 받고, arrs라는 3차원 리스트를 만들어서 토마토들의 상태를 저장한다.
3. 큐 초기화:
   •  익은 토마토(1)를 큐에 모두 넣어준다. 익은 토마토를 중심으로 bfs를 돌려야하니까.
4. BFS 함수:
   •  bfs를 통해 익은 토마토가 주변의 익지 않은 토마토를 익혀가면서 며칠이 걸리는지 계산.
5. 최종 결과 계산:
   •  bfs를 다 돌고 나서, 익지 않은 토마토가 남아있으면 -1을 출력하고, 그렇지 않으면 가장 오래 걸린 날에서 1을 뺀 값을 출력( 처음 시작할 때의 상태가 이미 1로 시작하기 때문에 실제로 걸린 날짜를 구하려면 마지막에 1을 빼줘야 함).

 

7576번 토마토와 유사한 문제인데 

이 문제는 상자를 쌓아서 3차원배열로 만들었다.!

그부분만 유의해서 코드를 쓰면 OK