[백준 알고리즘 ] 7569. 토마토

 

 

 

 

3차원 배열로 풀어야 했고, 방향은 위, 아래 / 앞, 뒤 / 왼쪽, 오른쪽 해서 총 6방향이었다.

 

기존에 2차원 배열과 4방향을 사용해서 푼 걸 응용해서 풀었더니 어렵지 않게 풀었다.

 

 

 

1) 익은 토마토를 찾아서 Q 에 넣어주고

 

2) Q를 사용하여 인접한 토마토가 다 익는데 걸리는 날을 측정해 답을 구함.

 

3) 안익은 토마토가 있을 경우, 답을 -1로 바꿈.

 

 

 

 

처음부터 안익은 토마토가 없는 경우가 존재하는데, 아래 코드에서는 이를 따로 처리해주지 않았다.

 

날짜를 셀때 -1로 시작하기에 안익은 토마토가 없는 경우에는 기존의 있던 토마토가 한번씩 pop되서 돌아서 cnt 값이 0으로 바뀌기 때문이다.

 

 

 

from collections import deque


def find_riped_tomatoes():
    for floor in range(H):  # 층수
        for i in range(N):  # ROW값
            for j in range(M):  # COL값
                # 익은 토마토 찾기
                if tomatoes[floor][i][j] == 1:
                    Q.append((floor, i, j))

    return

def make_tomatoes_riped():
    cnt = -1
    while Q:
        cnt += 1
        size = len(Q)
        for i in range(size):
            f, r, c = Q.popleft()
            for dt in range(6):
                nf = f + delta[dt][0]
                nr = r + delta[dt][1]
                nc = c + delta[dt][2]
                if 0 <= nr < N and 0 <= nc < M and 0 <= nf < H:
                    if tomatoes[nf][nr][nc] == 0:
                        tomatoes[nf][nr][nc] = 1
                        Q.append((nf, nr, nc))
    return cnt

# 아직도 안익은 토마토 찾기
def check_toamtes(ans):
    for floor in range(H):  # 층수
        for i in range(N):  # ROW값
            for j in range(M):  # COL값
                if tomatoes[floor][i][j] == 0:
                    return -1
    return ans

delta = [(0, 1, 0), (0, 0, 1), (0, 0, -1), (0, -1, 0),(1, 0, 0), (-1, 0, 0)]
M, N, H = map(int, input().split())
tomatoes = []
Q = deque()

# 토마토 값 저장
for i in range(H):
    box = []
    for j in range(N):
        box.append(list(map(int, input().split())))
    tomatoes.append(box)

find_riped_tomatoes()
ans = check_toamtes(make_tomatoes_riped())

print(ans)