[파이썬]백준 7569 토마토

링크

백준 7569 토마토

7576번을 풀기 전에 이문제에 먼저 도전했었는데 잘 안풀려서 7576토마토를 먼저 풀어보니 단순히 해당 문제를 3차원으로 구현만 하면 되는 문제였다.
7576토마토와 똑같이 토마토(1)가 있는 좌표를 미리 큐에 담아놓고 해당 큐를 bfs로 탐색했다.

정답 코드

import sys
from collections import deque

def bfs(q):
    global maxd
    # 위 아래 북 동 남 서
    dh = [-1, 1, 0, 0, 0, 0]
    dr = [0, 0, -1, 0, 1, 0]
    dc = [0, 0, 0, 1, 0, -1]

    while q:
        h, r, c = q.popleft()
        for i in range(6):
            nh = h + dh[i]
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nh < H and 0 <= nr < N and 0 <= nc < M and box[nh][nr][nc] == 0:
                box[nh][nr][nc] = 1
                distance[nh][nr][nc] = distance[h][r][c] + 1
                q.append([nh, nr, nc])

                if distance[nh][nr][nc] > maxd:
                    maxd = distance[nh][nr][nc]


def check(arr):
    for i in range(H):
        for j in range(N):
            for k in range(M):
                if arr[i][j][k] == 0:
                    return -1

#가로 세로 높이
M, N, H = map(int, sys.stdin.readline().split())
floor = [] #층
box = [] #전체
q = deque() #탐색을 시작할 좌표
distance = [[[0] * M for _ in range(N)] for __ in range(H)] #거리체크
maxd = 0 #최대거리


for h in range(H):
    for r in range(N):
        floor.append(list(map(int, sys.stdin.readline().split())))
        for c in range(M):
            if floor[r][c] == 1:
                q.append([h, r, c])
    box.append(floor)
    floor = []

bfs(q)
if check(box) == -1:
    print(-1)
else:
    print(maxd)

알게된 것👨‍💻

• 고차원이 되면 겁을먹고 단순한 해결방법도 못찾는 경우가 생기는데 이럴땐 조금 단순화해서 다시생각해보자
  해결방법만 찾는다면 몇차원이든 풀수있다.