[백준/파이썬] 7569번: 토마토

문제

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

풀이

• M×N 사이즈 토마토 상자
• 토마토 보관 후, 하루마다 익은 토마토 주위 토마토(위, 아래, 왼쪽, 오른쪽, 앞, 뒤)가 익음
• 토마토가 모두 익는 최소 일수
• 1: 익은 토마토, 0: 익지 않은 토마토, -1: 빈 칸

7576번: 토마토의 3차원 버전 문제
위 문제와 마찬가지로 BFS로 풀면 됩니다.(토마토가 모두 익는 최수 일수)

토마토를 모든 상자에 담아줍니다.

m,n,h = map(int,input().split()) # 가로, 세로, 높이
box = [[list(map(int,input().split())) for _ in range(n)]

입력 받은 토마토를 모두 탐색하여 익은 토마토(1)의 위치를 queue에 담아줍니다.

queue = deque()
for i in range(h):
    for j in range(n):
		for k in range(m):
			if box[i][j][k] == 1:
		        queue.append((i,j,k))

queue에 익은 토마토의 모든 좌표를 담았으니, BFS를 이용해 모든 토마토를 탐색합니다.

def bfs():
    dx = [-1,1,0,0,0,0]
    dy = [0,0,-1,1,0,0]
    dz = [0,0,0,0,-1,1]
    

3차원 배열의 탐색을 위해서는 z축도 탐색해야 되므로 dz를 선언해주어야 합니다.

queue에 저장된 좌표를 가지고 탐색

    while queue:
        x,y,z = queue.popleft() # 탐색을 진행할 좌표
        
        # 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 탐색
        for i in range(6): 
            nx,ny,nz = x+dx[i],y+dy[i],z+dz[i]
            if 0 <= nx < h and 0 <= ny < n and 0 <= nz < m and box[nx][ny][nz] == 0: # 범위 내 && 익지 않은 토마토일 경우
                queue.append((nx,ny,nz)) # 익은 토마토 좌표 추가
                box[nx][ny][nz] = box[x][y][z] + 1 # 이전 값 + 1

탐색을 마친 후 최대값을 출력해줍니다.

문제에서 모든 과일이 익지 않았을 경우(0이 존재할 경우) -1을 출력하라고 했으니 유의하세요 😋

res = 0
for a in box:
    for b in a:
		if 0 in b:
		    print(-1)
            exit()
	res = max(res, max(b))
print(res - 1)

처음 입력 받을 때 익은 과일을 1로 선언하고 이 값을 증가시켜 결과를 도출해냈으므로 res에서 1을 빼주어야 값이 올바르게 나옵니다. ☺️

코드

from collections import deque
import sys
input = sys.stdin.readline

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

if __name__ == "__main__":
    m,n,h = map(int,input().split()) # 가로, 세로, 높이
    
    box = [[list(map(int,input().split())) for _ in range(n)] for _ in range(h)]
    
    queue = deque()
    for i in range(h):
        for j in range(n):
            for k in range(m):
                if box[i][j][k] == 1:
                    queue.append((i,j,k))
                
    bfs()
    
    res = 0
    for a in box:
        for b in a:
            if 0 in b:
                print(-1)
                exit()
            res = max(res, max(b))
    print(res - 1)