[백준] 7569. 토마토 - 파이썬

https://www.acmicpc.net/problem/7569

 

풀이

[백준 3197 - 백조의 호수] 문제와 상당히 유사했던 문제.

BFS를 이용해 풀이함.

 

주의할 점은, 토마토를 익히는 과정에서 한 번 익혀지고, queue에 들어간 토마토는 값이 이미 1이 되었기 때문에,

visited나 queue에 이미 존재하는 지 확인할 필요가 없음.

in 이나 not in 연산자는 O(N) 의 time complexity를 가지므로, for나 while문 안에서 남발했다가는 그대로 시간초과가 되기 쉽다.

 

[백준 3197 - 백조의 호수] 보다 쉬웠던 점은, 토마토가 다 익었는지 확인하는 과정을 Brute-Force로 처리해도 되었음.

그러나 3차원 배열을 써야 하므로 index의 순서가 바뀌지는 않았는지 항상 유의하자.

 

import copy
from collections import deque

width, height, depth = map(int, input().split())
box = []
for _ in range(depth):
    box.append([list(map(int, input().split())) for _ in range(height)])


# 시작 상황에서 모든 익은 토마토의 좌표를 queue에 push
deq = deque([])
for z, d in enumerate(box):
    for y, h in enumerate(d):
        for x, w in enumerate(h):
            if w == 1:
                # z, y, x 좌표순
                deq.append([z, y, x])

# 토마토의 좌표는 box[z][y][x]입니다.
dx = [1, 0, 0, -1, 0, 0]
dy = [0, 1, 0, 0, -1, 0]
dz = [0, 0, 1, 0, 0, -1]

cnt = 0


def isFin(box):
    for a in box:
        for b in a:
            for c in b:
                if c == 0:
                    return False
    return True


while deq:
    # 토마토가 모두 익었으면
    if isFin(box):
        print(cnt)
        break
    cnt += 1

    # 이번에 전후좌우상하를 익힐 익은 토마토들 - deq_에 저장
    deq_ = copy.deepcopy(deq)
    # 오늘 익은 토마토들 - deq를 초기화시켜 저장
    deq = deque([])

    # 익은 토마토를 기준으로 전후좌우상하 6방향의 토마토를 익힘
    while deq_:
        z, y, x = deq_.popleft()
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
            # 이미 visit한 토마토는 box[nz][ny][nx] == 1 이기 때문에 pass. deq에도 push되지 않음.
            if 0 <= nx < width and 0 <= ny < height and 0 <= nz < depth and box[nz][ny][nx] == 0:
                box[nz][ny][nx] = 1
                deq.append([nz, ny, nx])


# 토마토가 모두 익지 않았으면
if not isFin(box):
    print(-1)