백준 7569번 토마토

문제

해결방법

입력받은 배열을 탐색하여 토마토가 있는 곳부터 탐색을 시작한후, bfs를 사용하여 큐에 새로운좌표와, 익히는 일수를 하나씩 더해주면서 탐색한다.

마친 후에는 익지 않은 토마토가 있는지 배열을 다시 한번 탐색하여 있다면 -1 그렇지 않다면 익히는데 걸린 총 일수를 출력한다.

from collections import deque
import sys
n,m,h = map(int,sys.stdin.readline().split())
graph = [[list(map(int,sys.stdin.readline().split())) for _ in range(m)] for _ in range(h)]
queue = deque()
# 동서남북전후
dy = [0, 0, -1, 1, 0, 0]
dx = [1, -1, 0, 0, 0, 0]
dh = [0, 0, 0, 0, 1, -1]

def bfs():
# 토마토 들어있는 칸  탐색해서 찾으면
# 좌표와 현재일수 (0일 삽입)
    for i in range(h):
        for j in range(m):
            for k in range(n):
                if graph[i][j][k] == 1:
                    queue.append((i, j, k, 0))

    while queue:
        z, y, x, d = queue.popleft()
        # 토마토의 동서남북전후 탐색
        for i in range(6):
            new_z = z + dh[i]
            new_y = y + dy[i]
            new_x = x + dx[i]
            # 안 익은 토마토 탐색해서 좌표와 날짜 + 1을 큐에 삽입
            if 0 <= new_z < h and 0 <= new_y < m and 0 <= new_x < n and graph[new_z][new_y][new_x] == 0:
                graph[new_z][new_y][new_x] = 1
                queue.append((new_z, new_y, new_x, d + 1))

# bfs로 탐색하면서 0을 가진 값을 1로 바꺼주고
# 그래도 0인 값이 하나라도 있다면 -1 리턴
# 나머지 경우에는 익히는데 걸린 날짜 출력
    for i in range(h):
        for j in range(m):
            for k in range(n):
                if graph[i][j][k] == 0:
                    return -1
    return d

print(bfs())