[알고리즘][Python] 백준 7569 토마토(3차원) 문제 풀이

문제 출처 : www.acmicpc.net/problem/7569

7569번: 토마토

---

문제 해석 : 토마토가 익는 것은 주변에 익은 토마토에 의해서 이루어진다. 따라서 모든 토마토가 익을 때 까지 걸리는 시간을 출력하는 문제이다.

 

문제 풀이 :  전형적인 BFS 문제이지만 3차원이기 때문에 인덱싱을 조심해서 풀면 풀 수 있다.

---

풀이 코드

from collections import deque

def BFS():
    while Q:
        x,y,z = Q.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:
                if arr[nx][ny][nz] == 0:
                    arr[nx][ny][nz] = arr[x][y][z] + 1
                    Q.append((nx,ny,nz))


M, N, H = map(int, input().split())
arr = [[] for _ in range(H)]
for i in range(H):
    for _ in range(N):
        arr[i].append(list(map(int, input().split())))

dx = [0,0,0,0,1,-1]
dy = [0,0,1,-1,0,0]
dz = [1,-1,0,0,0,0]

answer = 0
Q = deque()

for i in range(H):
    for j in range(N):
        for k in range(M):
            if arr[i][j][k] == 1:
                Q.append((i,j,k))

BFS()
Flag = False

for i in range(H):
    for j in range(N):
        for k in range(M):

            if arr[i][j][k] == 0:
                Flag = True
                break
            answer = max(answer, arr[i][j][k])

if Flag:
    answer = -1
elif answer == -1:
    answer = 0
else:
    answer -= 1

print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.