[Python/백준] 7569. 토마토 3차원

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

DFS/BFS

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

---

풀이

유사 3차원 실제는 2차원 풀이

from collections import deque
import sys
input = sys.stdin.readline

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

# 아래 반복문 list comprehension으로 개선하기!!
box = []
for _ in range(N * H):
    box.append(list(map(int, input().split())))

# 층을 고정한 상태에서, 행을 고정한 상태에서, 열을 기준으로 먼저 돌린다!!
queue = deque((i, j, k, 0) for k in range(H) for i in range(N) for j in range(M) if box[i + N * k][j] == 1)

# '상 하 좌 우 윗칸 아래칸' 델타값 정의
dx, dy, dz = [-1, 1, 0, 0, 0, 0], [0, 0, -1, 1, 0, 0], [0, 0, 0, 0, -1, 1]

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

for line in box:
    if line.count(0):
        print(-1)
        exit(0)

print(t)

실제 3차원으로 리스트 풀이

from collections import deque
import sys
input = sys.stdin.readline

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

# 아래 반복문 list comprehension으로 개선하기!!
box = [[] for _ in range(H)]
for h in range(H):
    for _ in range(N):
        box[h].append(list(map(int, input().split())))

# 층을 고정한 상태에서, 행을 고정한 상태에서, 열을 기준으로 먼저 돌린다!!
queue = deque((i, j, k, 0) 

for k in range(H) for i in range(N) for j in range(M) if box[k][i][j] == 1)

# '상 하 좌 우 윗칸 아래칸' 델타값 정의
dx, dy, dz = [-1, 1, 0, 0, 0, 0], [0, 0, -1, 1, 0, 0], [0, 0, 0, 0, -1, 1]

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


# for line in box:
#     if line.count(0):
#         print(-1)
#         exit(0)

for layer in box:
    for line in layer:
        if line.count(0):
             print(-1)
             exit(0)
print(t)

이 문제는 3차원으로 푸는 게 더 직관적,

처음에는 2차원 풀이가 떠올라 2차원으로 해결했으나,

실제 현장에선 둘 중 어느 풀이든 떠오르는 풀이로 풀면 될 듯하나,

그러나, 3차원 풀이가 더 직관적이고 실수를 줄일 수 있는 풀이로 판단되니,

다음에 유사 문제에서 두 풀이가 전부 떠올랐다면 되도록 3차원 풀이로 풀자.

---

250221 재풀이

from collections import deque
import sys
input = sys.stdin.readline

# 1이 0을 1으로 만들어나가며 -1은 벽인 BFS 델타 탐색 문제

m, n, h = map(int, input().split())
tomato = [[list(map(int, input().split())) \
for _ in range(n)] for _ in range(h)]

queue = deque([(k, i, j, 0) for k in range(h) \
for i in range(n) for j in range(m) if tomato[k][i][j] == 1])

# 상 하 좌 우 위층 아래층 델타값 정의
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
# 층 또한 가장 위쪽 칸이 index 0이란 관점으로 가자.

# 2. queue가 빌 때까지:
while queue:
    # 3. pop하며 해당 정점에서 action 실행
    z, x, y, t = queue.popleft()
    # 4. 인접한 모든 정점들에 대해,
    for i in range(6):
        nz = z + dz[i]
        nx = x + dx[i]
        ny = y + dy[i]
        # 5. 방문x 인접 정점들로 이동
        if 0 <= nz < h and 0 <= nx < n and 0 <= ny < m \
        and tomato[nz][nx][ny] == 0:
            tomato[nz][nx][ny] = 1
            queue.append((nz, nx, ny, t + 1))

# for layer in tomato:
#     for line in layer:
#         if 0 in line:
#             t = -1

def is_there_any_unripe_tomato():
    for layer in tomato:
        for line in layer:
            if 0 in line:
                global t
                t = -1
                return
            # early return 구현 -> 발견하면 즉시 빠져나와 더 효율적

is_there_any_unripe_tomato()
print(t)