[백준] 7569번: 토마토 - Python

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

아이디어

• 익은 토마토를 기준으로 주변으로 퍼지며 익는 현상이 이전에 바이러스 문제랑 비슷
• BFS를 활용해서 풀면 될듯함
• 3차원 배열을 선언 후 익은 토마토의 위치틀을 큐에 저장
• 큐를 기준으로 BFS를 진행
  • 6방향을 모두 탐색하며 진행한다
  • 익지않은 토마토를 발견하면 이전 토마토의 수에서 +1한 값을 저장해둔다.
  • 이는 며칠째 익은 토마토인지 확인 할 수 있는 지표가 됨
• BFS를 모두 마친 후 모든 토마토가 익었는지 판단
• 익지 않은 토마토가 있으면 -1 반황
• 그렇지 않으면 배열의 최대값을 반환해준다.

구현

from collections import deque

M, N, H = map(int, input().split())

box = [[list(map(int,input().split())) for _ in range(N)] for _ in range(H)]


# 익은 토마토 위치 탐색
tomatos = deque()
for i in range(H):
    for j in range(N):
        for k in range(M):
            if box[i][j][k] == 1:
                tomatos.append((i,j,k))


# bfs 진행
dz = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dx = [0, 0, 0, 0, -1, 1]

while tomatos:
    z, y, x = tomatos.popleft()
    for i in range(6):
        nz  = z + dz[i]
        ny  = y + dy[i]
        nx  = x + dx[i]
        if 0<=nz<H and 0<=ny<N and 0<=nx<M:
            if box[nz][ny][nx] == 0:
               box[nz][ny][nx] = box[z][y][x] + 1
               tomatos.append((nz, ny, nx))


# 0이 있으면 -1 없으면 최대값 도출
result = 0
for i in range(H):
    for j in range(N):
        for k in range(M):
            if box[i][j][k] == 0:
                print(-1)
                exit()
            result = max(result, box[i][j][k])

print(result-1)

 

마무리

기존의 BFS문제와 다른게 3차원 배열이였다는 점 빼고는 크게 다른점이 없는 문제였다.

굳

범위 (n)의 J의 경우 : 범위 (m)의 k의 경우 :