[골드 V] 7569번. 토마토

 문제 

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

7569번: 토마토

 사용 언어 

Python3

 풀이 과정 

이 문제는 2차원 배열로 푸는 버전도 있는 것 같지만 우리는 바로 3차원 배열로 푸는 버전이 숙제였다.

3차원 배열을 선언하는 것도, 거기에 vector값을 이용해 bfs를 사용하는 것도 처음이어서 검색을 좀 했다.

list comprehension이 참 깔끔한 파이썬!

 

처음에는 아래처럼 모든 토마토가 저장될 때부터 익어있을 때 0을 출력하도록 하는 if문을 추가했는데, 이게 잘못된 로직이었다. -1인(토마토가 없는) 경우도 있기 때문에 이렇게 확인할 수 없다.

# 저장될 때부터 모든 토마토가 익어있다면 0 출력
if len(q) == H * M * N:
    print(0)
    exit()
else:
    bfs()

그래서 그 부분 삭제하고 또 틀려서 보니 for문 안의 코드 들여쓰기 위치도 수정해서 맞았습니다!!

 

 제출 답안 

# 1은 익은 토마토 / 0은 익지 않은 토마토 / -1은 토마토가 들어있지 않은 칸
from collections import deque
from sys import stdin
input = stdin.readline

M, N, H = map(int, input().split())
# 토마토 박스 상태 3차원 배열
array = [[list(map(int, input().split())) for _ in range(N)] for _ in range(H)]

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

q = deque()
def bfs():
    while q:
        z, x, y = q.popleft()
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
            if 0 <= nx < N and 0 <= ny < M and 0 <= nz < H:
                # 익은 토마토의 다음 칸의 토마토를 익힘
                # 이미 익은 토마토여도 계속 더해지는게 포인트!
                if array[nz][nx][ny] == 0:
                    array[nz][nx][ny] = array[z][x][y] + 1
                    q.append((nz, nx, ny))

for i in range(H):
    for j in range(N):
        for k in range(M):
            # 익은 토마토들이 있는 위치를 q에 추가
            if array[i][j][k] == 1:
                q.append((i, j, k))

bfs()

day = 0
for i in range(H):
    for j in range(N):
        for k in range(M):
            # 끝까지 익지 않은 토마토가 있다면 -1 출력
            if array[i][j][k] == 0:
                print(-1)
                exit()
            day = max(day, array[i][j][k])

# 최대값은 처음부터 익어있던 토마토 중에 나오기 때문에 1을 빼줘야 함
print(day - 1)

 

 공부한 내용 

3차원 배열

파이썬에서 3차원 배열을 선언하는 데에는 3가지 방법이 있었다.

 

1. list comprehension

array = [[[0 for k in range(n)] for j in range(n)] for i in range(n)]

 

2. 곱셈

array = [[[0]*n]*n]*n

 

3.  Numpy 패키지

 

* 외부 설치 패키지이기 때문에 코딩테스트 환경에서는 작동하지 않을 것

import numpy as np

i = 3
j = 3
k = 3

new_array= np.zeros((i, j, k))

 

나는 1번 list comprehension을 사용했는데 2번이 좀더 빠를것도 같아서 바꿔보려 했지만 input을 받으면서 *를 사용하면 같은 값이 반복되어 불가능한 것 같았다...? 따라서 일단 다음과 같은 방식을 기억해둬야겠다.

array = [[list(map(int, input().split())) for _ in range(N)] for _ in range(H)]

 

출처: https://www.delftstack.com/ko/howto/python/declare-3d-array-in-python/