[BOJ]7569. 토마토

문제:

2019/10/29 - [Algorithm/Python] - [BOJ]7576. 토마토

 

 위 문제에서 더 발전한 문제로 이제 한 층이 아닌 여러 층에 대해서 토마토가 익는 것이 전이된다.

입력:

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2<=M<=100,2<=N<=100,1<=H<=100이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

출력: 

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산하여 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

풀이방법:

 이전문제에선 2차원 배열로 받았지만, 이번에는 3차원 배열로 작성한다. 또한 위, 아래로도 이동해야 하기 때문에 dx,dy,dn 세 가지 변수를 사용했다. 이외에는 이전문제와 동일한 풀이로 풀었다.

import sys
m,n,h=map(int,sys.stdin.readline().split())
tomatos=[]
for j in range(h):
    temp=[]
    for i in range(n):
        t=list(map(int,sys.stdin.readline().split()))
        temp.append(t)
    tomatos.append(temp)
queue=[]
for k in range(h):
    for i in range(n):
        for j in range(m):
            if tomatos[k][i][j]==1:
                queue.append((k,i,j))
dx=[0,0,0,0,-1,1]
dy=[0,1,0,-1,0,0]
dh=[1,0,-1,0,0,0]
count=0
while len(queue)!=0:
    count+=1
    temp=[]
    change=False
    for k,i,j in queue[:]:
        for c in range(6):
            nx=j+dx[c]
            ny=i+dy[c]
            nh=k+dh[c]
            if 0<= ny < n and 0<= nx < m and 0<=nh < h:
                if tomatos[nh][ny][nx]==0:
                    tomatos[nh][ny][nx]=1
                    temp.append((nh,ny,nx))
                    change=True
    queue.pop(0)
    queue=temp
    if not change:
        break
        
remain=False
for k in range(h):
    for i in range(n):
        for j in range(m):
            if tomatos[k][i][j]==0:
                remain=True
                break
if not remain:
    print(count-1) 
else:
    print(-1)

문제링크:

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