[BOJ] 7569. 토마토

문제

토마토 (https://www.acmicpc.net/problem/7569)

풀이

1. 초기 접근

• 문제조건 해석
  • 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다.
    • BFS 문제다.
• 알고리즘
  • 가장 기초적인 BFS 문제라고 생각된다.
  • 이전 7576. 토마토 문제에서 위아래 방향만 추가한 것이다.
• 코드

import sys
from collections import deque

dzs = [0, 0, 0, 0, 1, -1]
dxs = [-1, 0, 1, 0, 0, 0]
dys = [0, -1, 0, 1, 0, 0]

m, n, h = map(int, sys.stdin.readline().split())
board, q, visited = [], deque(), set()

for _ in range(h):
    floor = []
    for _ in range(n):
        floor.append(list(map(int, input().split())))
    board.append(floor)

for k in range(h):
    for i in range(n):
        for j in range(m):
            if board[k][i][j] == 1:
                q.append((k, i, j))
                visited.add((k, i, j))

def bfs():
    step = 0
    while q:
        size = len(q)

        for i in range(size):
            z, x, y = q.popleft()

            for dz, dx, dy in zip(dzs, dxs, dys):
                nz, nx, ny = z + dz, x + dx, y + dy

                if nx >=0 and nx < n and ny >= 0 and ny < m and nz >=0 and nz < h and\
                    (nz, nx, ny) not in visited and board[nz][nx][ny] != -1:
                    visited.add((nz, nx, ny))
                    q.append((nz, nx, ny))
                    board[nz][nx][ny] = 1
        step += 1

    for k in range(h):
        for i in range(n):
            for j in range(m):
                if board[k][i][j] == 0:
                    return -1
    return step - 1

print(bfs())