[백준/Python] 7569. 토마토

 

 

• BFS를 3차원배열을 이용하여 풀었다

 

from collections import deque

M,N,H = map(int,input().split())
tomato = []
q = deque()
directy = [-1,1,0,0,0,0]
directx = [0,0,1,-1,0,0]
directk = [0,0,0,0,-1,1]
mmax,flag = 0,0
used = [[[0] * M for _ in range(N)] for _ in range(H)] # 방문체크

for j in range(H): # tomato라는 변수에 3차원 정보 저장
    arr = []
    for i in range(N):
        tmp = list(map(int,input().split()))
        arr.append(tmp)
    tomato.append(arr)

for k in range(H): # 완전탐색을 통해 초기 토마토 위치를 q에 저장
    for j in range(N):
        for i in range(M):
            if tomato[k][j][i] == 1:
                used[k][j][i] = 1
                q.append([k,j,i])

def bfs():
    global mmax,cnt

    while q:
        k,y,x = q.popleft()

        for l in range(6):
            dy = directy[l] + y
            dx = directx[l] + x
            dk = directk[l] + k

            if dy >= N or dy < 0 or dx >= M or dx < 0 or dk >= H or dk < 0: # 배열 벗어나면 continue
                continue
            if tomato[dk][dy][dx] == -1: # 토마토가 없는 곳이라면 continue
                continue
            if used[dk][dy][dx] == 0: # 방문하지 않았던 곳이라면
                used[dk][dy][dx] = 1 # 방문 체크 하고
                tomato[dk][dy][dx] = tomato[k][y][x] + 1
                if mmax < tomato[dk][dy][dx]:
                    mmax = tomato[dk][dy][dx]
                q.append([dk,dy,dx]) # q에 추가


bfs()

for k in range(H): # bfs를 호출하고 난 후 다시 완전탐색으로 안익은 토마토 확인
    for j in range(N):
        for i in range(M):
            if tomato[k][j][i] == 0: 
                flag = 1

if flag: # 안익은 토마토가 있다면 
    print(-1)
else:
    if mmax == 0: # 처음부터 익은 토마토 밖에 없는 경우
        print(0)
    else:
        print(mmax-1)