문제 : https://www.acmicpc.net/problem/7569
이 문제는 https://www.acmicpc.net/problem/7576
의 업그레이드 버전인거 같다. 과거 단수 bfs만으로 풀었더 7576번 문제에서 살짝 코드를 변경해서 풀었다. 풀이과정은 다음과 같다
from collections import deque
m,n,h = map(int,input().split())
board = [None for _ in range(h)]
q = deque()
total_num = 0
reap_num = 0
for k in range(h):
_board = []
for i in range(n):
temp = list(map(int,input().split()))
for j in range(m):
if temp[j]!=-1:
total_num+=1
if temp[j]==1:
q.append(((k,i,j),0))
_board.append(temp)
board[k]= _board
d_list = [[1,0,0],[-1,0,0],[0,-1,0],[0,1,0],[0,0,-1],[0,0,1]]
visit = [[[False]*m for _ in range(n)] for _ in range(h)]
while q:
(k,y,x),cnt = q.popleft()
if visit[k][y][x]:
continue
visit[k][y][x]=True
reap_num+=1
for d in d_list:
nk = k+d[0]
ny = y+d[1]
nx = x+d[2]
if 0<=nk<h and 0<=ny<n and 0<=nx<m:
if not visit[nk][ny][nx]:
if board[nk][ny][nx]==0:
board[nk][ny][nx]=1
q.append(((nk,ny,nx),cnt+1))
if total_num!=reap_num:
print(-1)
else:
print(cnt)
일단 dy,dx가 아닌 dk,dy,dx로 3차원으로 움직여야된다. 그리고 모든 토마토를 일일히 검사하지 않고 개수를 세서 모두 익었는지 확인하면 끝!!
사실 3차원이여서 구현하기 까다로울 수 있으나 단순 bfs구현문제라서 난이도가 쉬운편에 속한다고 생각한다.