토마토 [백준 7569]

1. 문제 접근 방법

- 토마토(백준 7576) 하고 비슷한 문제이다.

  차이점은 토마토가 3차원 리스트에 들어 있다는 차이점이 있다

  3차원 리스트에서 6가지 방향으로 탐색하는 것만 잘 고려하면 되는 문제라고 할 수 있다. 

 

 

2. 코드

from collections import deque

M, N, H = map(int, input().split())

board = []
count = [[[0 for col in range(M)] for row in range(N)] for depth in range(H)]

q = deque()

## 3차원 탐색을 위한 dx,dy,dz를 정해준다. 
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, 0, 0, 1, -1]
dz = [0, 0, -1, 1, 0, 0]

for i in range(H):
    
    tmpBoard = [] 
    
    ## 입력값을 tmpBoard라는 2차원 리스트에 담는다 
    for j in range(N):
        row = list(map(int, input().split()))
        tmpBoard.append(row)
    
    ## tmpBoard를 board에 담는다
    ## 이로써, board는 3차원 리스트가 되고, 
    ## 초기 입력값을 저장한다 
    board.append(tmpBoard)
    
    
    
## 초기 board 중에서 1인 값을 
## 큐에 넣어준다. 
## 그리고 해당 위치의 count를 1로 저장한다 
for i in range(H):
    for j in range(N):
        for k in range(M):
            if board[i][j][k] == 1:
                q.append([i, j, k])
                count[i][j][k] = 1 
        

while q:
    
    x, y, z = q.popleft()
    
    ## q에 들어 있는 값에 대하여, 6가지 방향에 대해서 탐색을 진행한다
    ## 탐색했을 때, 0인 곳은 다음 방문할 곳으로 지정하여, 큐에 넣어준다.
    ## 그리고 board에는 토마토가 확산되었다는 의미로 1을 추가한다. 
    for i in range(6):
        nx = x + dx[i]
        ny = y + dy[i]
        nz = z + dz[i]
        
        if 0<=nx and nx < H and 0<=ny and ny < N and 0<=nz and nz < M and count[nx][ny][nz] == 0 and board[nx][ny][nz] == 0:
            count[nx][ny][nz] = count[x][y][z] + 1 
            board[nx][ny][nz] = 1 
            q.append([nx, ny, nz])
            
isAble = True 

## board 중에서 0인 곳이 1곳이라도 있다면
## 모두 익지는 못하는 상황이므로 isAble 변수를 False로 처리한다. 
for i in range(H):
    for j in range(N):
        for k in range(M):
            if board[i][j][k] == 0:
                isAble = False 
                
## 모두 익을 수 있는 상황이라면, 
## count에서 가장 작은 값을 골라준다. 
if isAble == True: 
    minDay = -int(1e9)
    
    for i in range(H):
        for j in range(N):
            for k in range(M):
                minDay = max(minDay, count[i][j][k])

    print(minDay-1)

## 모두 익을 수 없는 상황이라면, -1을 출력한다. 
else:
    print(-1)