Jin의 일상

문제

1. x, y, z 방향으로 BFS를 실행하는 문제다.

2. x, y는 격자무늬 상자 안에 있는 토마토의 좌표를 의미하며, z는 겹쳐 올린 상자의 층을 뜻한다.

3. 상자 안에 있는 토마토는 0, 1, -1의 상태를 가진다. 

(0 : 토마토가 익지 않았다,  1 : 토마토가 익었다,  -1 : 토마토가 존재하지 않는다)

4. 토마토는 매일 "상/하/좌/우/위/아래" 방향으로 전염되어 익는다.

5. 토마토가 익는 데 걸리는 최소 일 수을 출력한다. 

 - 처음부터 모든 토마토가 익었으면 0을 출력한다. 

 - 모든 토마토를 익히지 못한다면 -1을 출력한다. 

알고리즘

1. 3차원 배열에서의 BFS만 구현하면 된다. (기본 2차원 배열에서 배열을 하나 더 추가한 것이다.)

1. 익은 토마토의 좌표를 리스트에 담는다.

2. 익은 토마토를 중심으로 상/하/좌/우/위/아래로 좌표를 이동시킨다.

3. 이동한 좌표가 좌표평면에서 벗어나지 않는다면 계속 진행한다.

4. 이동 전 익은 토마토의 좌표의 값에 1을 더하여 이동 후의 좌표 평면에 1을 더해준다. (매일 주변에 있는 토마토가 익으므로, 좌표평면에 존재하는 값은 "지난 일수"를 의미 한다.)

5. 좌표를 이동함으로써 익게 된 토마토의 좌표를 리스트에 담는다.

6. x, y, z 방향으로 3중 반복문을 실행하여 토마토가 전부 익었는지 확인한다.

 - 모두 익지 않았다면 -1을 출력하고 프로그램을 종료한다. 

7. 최대 값(mx)을 1로 초기화한다.

 - 문제 조건에서 처음부터 토마토가 모두 익었으면 0을 출력하라고 했다.

8. x, y, z 방향으로 3중 반복문을 실행하여, mx와 비교하며 좌표 평면에서 가장 큰 수(익는데 걸린 일수)를 찾는다.

9. mx - 1을 해서 정답을 출력한다.

  - 시작 시에 좌표평면의 값이 1이므로, 익는데 걸린 시간에 포함시키지 않는다.

코드

import sys
from collections import deque
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def BFS():
    while queue:
        x, y, z = queue.popleft()
        for dx, dy, dz in mv:
            xx = x + dx
            yy = y + dy
            zz = z + dz
            if 0 <= xx < col and 0 <= yy < row and 0 <= zz < height and board[zz][yy][xx] == 0:
                board[zz][yy][xx] = board[z][y][x] + 1
                queue.append([xx, yy, zz])

if __name__ == '__main__':
    col, row, height = map(int, input().split())
    board = [[list(map(int, input().split())) for _ in range(row)] for _ in range(height)]
    mv = ((1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1))

    # 익은 것의 좌표를 찾는다.
    queue = deque()
    for y in range(row):
        for x in range(col):
            for z in range(height):
                if board[z][y][x] == 1:
                    queue.append([x, y, z])

    BFS()
    # 모두 다 익었는지 확인한다.
    for y in range(row):
        for x in range(col):
            for z in range(height):
                if board[z][y][x] == 0:
                    print(-1)
                    sys.exit()

    # 걸린 일수를 출력한다.
    mx = 1
    for z in range(height):
        for y in range(row):
            mx = max(mx, max(board[z][y]))
    print(mx-1)