[백준] 7576번: 토마토

토맛토마토 vs 토마토맛토

문제보기

bfs 문제였다. 전에 비슷한 문제를 풀었었는데 뭐였는지 기억이 안난다.

이 문제는 다른 점이 다 익을 수 없는 경우도 있다는 거..?
그래서 그걸 마지막에 검사했다.

+) 나는 며칠이 걸리는 지 하나하나 다른 day 변수에 저장해서 큐에 넣어줬었는데, 다른 풀이들을 보니까 애초에 배열 값에 며칠이 걸렸는지 저장을 해놓는 방법이 있더라. -> 그 때 비슷한 그 문제도 그랬었다.(최단거리)

bfs에서 최단거리를 구하는 방식을 잊어버리지 말쟈!

from _collections import deque

M, N, H = map(int, input().split())
arr = []
tomato = deque()

for h in range(H):
    tmp = []
    for i in range(N):
        tmp.append(list(map(int, input().split())))
        for j in range(M):
            if tmp[i][j] == 1:
                tomato.append([h, i, j, 0])
    arr.append(tmp)

diff = [[1, 0, 0], [-1, 0, 0],
        [0, 1, 0], [0, -1, 0],
        [0, 0, 1], [0, 0, -1]]


def bfs():

    while tomato:
        z, x, y, day = tomato.popleft()
        for d in diff:
            newZ = z + d[0]
            newX = x + d[1]
            newY = y + d[2]
            if 0 <= newZ < H and 0 <= newX < N and 0 <= newY < M:
                if arr[newZ][newX][newY] == 0:
                    arr[newZ][newX][newY] = 1
                    tomato.append([newZ, newX, newY, day+1])

    able = True
    for l in arr:
        for r in l:
            if r.count(0): 
                able = False # 다 익지 않았으면 -1 출력

    if able:
        print(day)
    else:
        print(-1)

bfs()