[Python](BFS) 백준 7569번 : 토마토

---

<접근 방법>

1. 이전에 풀었던 토마토 문제에서는 2차원으로 접근한 반면, 이 문제에서는 3차원으로 접근하는 것만 바뀌었다.
2. 토마토가 비어있는 자리(arr[k][i][j] == -1)는 not_tomato += 1로 개수를 세고, 토마토가 있는 자리(arr[k][i][j] == 1)의 좌표는 tomato라는 리스트에 담아준다.
3. (BFS 안) tomato 리스트에 있는 좌표들을 방문처리(visited[k][i][j]=1)해주고, q에 담아준다.
4. 똑같이, 3차원 배열로 받고 bfs에서 퍼져나가는 범위는 위, 아래, 오른쪽, 왼쪽, 앞, 뒤로 설정하면 되겠다.
   위쪽(-1, 0, 0), 아래쪽(1, 0, 0), 앞쪽(0, -1, 0), 뒤쪽(0, 1, 0), 오른쪽(0, 0, 1), 왼쪽(0, 0, -1)
5. 방문처리는 '지난 일수 + 1'을 나타내고,
   bfs를 통해 익게 되는 토마토의 개수를 ripe에 +1을 해가며 더해주면
6. 원래 익어있던 토마토의 개수(len(tomato)), 익게 된 토마토(ripe), 토마토가 비어있는 자리(not_tomato)를 모두 더했을 때 전체 칸 수(H*N*M)와 같다면 며칠이 걸린 지 return 해주고,
   전체 칸 수와 다르다면(즉, 익지 못한 토마토가 존재한다면) -1을 return 한다.

from collections import deque

def bfs():
    visited = [[[0]*M for _ in range(N)] for _ in range(H)]     # 이때 visited에 적게 되는 수는 지나게 되는 일 수
    ripe = 0    # 익게 될 토마토의 개수
    q = deque()
    for k, i, j in tomato:
        visited[k][i][j] = 1
        q.append((k, i, j))

    while q:
        ch, cn, cm = q.popleft()
        for dh, di, dj in ((-1, 0, 0), (1, 0, 0), (0, -1, 0), (0, 1, 0), (0, 0, -1), (0, 0, 1)):    # 위, 아래, 뒤, 앞, 왼, 오른
            nh = ch + dh
            nn = cn + di
            nm = cm + dj
            # 범위 내, 미방문, 토마토가 존재하는 칸이라면
            if 0<=nh<H and 0<=nn<N and 0<=nm<M and not visited[nh][nn][nm] and arr[nh][nn][nm] == 0:
                q.append((nh, nn, nm))
                visited[nh][nn][nm] = visited[ch][cn][cm] + 1
                ripe += 1

    if not_tomato + ripe + len(tomato) == H*N*M:    # 토마토가 모두 익었을 시
        return visited[ch][cn][cm]-1
    else:   # 익지 않은 토마토가 존재할 시
        return -1


M, N, H = map(int, input().split())
arr = [[list(map(int, input().split())) for _ in range(N)] for _ in range(H)]
tomato = []
not_tomato = 0
for k in range(H):
    for i in range(N):
        for j in range(M):
            if arr[k][i][j] == 1:   # 토마토가 있는 좌표
                tomato.append((k, i, j))
            elif arr[k][i][j] == -1:    # 토마토가 비어있는 좌표
                not_tomato += 1
print(bfs())

예제 1의 visited 결과

이해가 되는 않는 부분이 있으면 질문 주세요. 감사합니다.