철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
설명
익은 토마토는 좌우앞뒤상하에 있는 하루동안 안 익은 토마토를 익게 만든다. 모든 토마토가 익을 때까지 걸리는 날을 출력하고 만약 안 익은 토마토가 하나라도 있으면 -1을 출력한다.
익은 토마토가 안 익은 토마토를 익게 만들고 그렇게 익은 토마토가 다시 주위에 있는 안 익은 토마토를 익게 만든다. 익은 토마토를 기준으로 주위를 한 칸씩 전염시키는 모습에서 BFS를 떠올릴 수 있다.
토마토의 최초 상태를 저장하는 3차원 배열을 생성한다. 모든 익은 토마토는 탐색의 출발점이 될 수 있다. 1일 경우 탐색 출발점으로 체크해준다. 또한 처음 안 익은 상태의 토마토의 개수도 세어준다. 최종적으로 안 익은 토마토가 있는지 확인하기 위함이다.
출발점을 기준으로 좌우앞뒤상하에 토마토가 존재하는지, 그리고 안 익은 토마토인지 확인한다. 만약 안 익은 토마토라면 익은 토마토로 바꾸고 3차원 배열에 익은 날을 저장한다. 이 토마토의 익은 날은 이 토마토를 익게 만든 토마토의 익은 날에서 1을 더한 값이다. 그리고 토마토를 익게 만들 때마다 익은 토마토의 개수를 세어준다.
최초의 안 익은 토마토의 개수와 익은 토마토의 개수가 다르다면 안 익은 토마토가 있다는 것이므로 -1을 출력한다.
개수가 같다면 다 익은 것이므로 tomato에 저장된 값 중 가장 큰 값에서 1을 뺀 값을 출력한다. 1을 빼는 이유는 최초에 익은 토마토가 1로 저장되기 때문이다.
코드
#7569번 토마토
from collections import deque
def BFS(tomato,start,m,n,h) :
x = [1,-1,0,0,0,0]
y = [0,0,1,-1,0,0]
z = [0,0,0,0,1,-1]
num = 0
q = deque(start)
day = 0
while q :
now = q.popleft()
for i in range(6) :
nx = now[2]+x[i]
ny = now[1]+y[i]
nz = now[0]+z[i]
if (nx >=0 and nx < m) and (ny >=0 and ny < n) and (nz >=0 and nz < h) :
if tomato[nz][ny][nx] == 0 :
q.append([nz,ny,nx])
tomato[nz][ny][nx] = tomato[now[0]][now[1]][now[2]]+1
day = max(day,tomato[nz][ny][nx])
num += 1
return num, day
if __name__ == "__main__":
m,n,h = map(int,input().split())
tomato = [[[0 for _ in range(m)] for _ in range(n)] for _ in range(h)]
start = []
zero = 0
for i in range(h) :
for j in range(n) :
tomato[i][j] = list(map(int,input().split()))
for l in range(m) :
if tomato[i][j][l] == 1 :
start.append([i,j,l])
elif tomato[i][j][l] == 0 :
zero += 1
answer = BFS(tomato,start,m,n,h)
if answer[0]!= zero :
print(-1)
elif answer[1] == 0 :
print(0)
else :
print(answer[1]-1)
