[Python]Baekjoon 7569번: 3차원 토마토(BFS)

1. 문제

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

7569번: 토마토

N, M 개의 칸에 토마토가 들어있고 이 상자를 H층만큼 쌓아 올린다.

0은 익지 않은 토마토, 1은 익은 토마토, -1은 빈칸을 의미한다.

익은 토마토와 인접해 있는(상, 하, 좌, 우, 위, 아래) 토마토는 하루가 지나면 익는다.

토마토가 모두 익는데 며칠이 걸릴까?

2. 풀이

최소 일수를 구하는 문제는 BFS를 이용한다.

7576번 토마토 문제와 동일한 로직으로 풀면 되지만 3차원인 점만 신경 써주면 된다.

첫 번째로 그래프와 visited를 3차원으로 초기화해줘야 하는데 이 부분을 신경 써줘야 한다.

여러 가지 방법이 있겠지만 가장 간단한 방법으로 초기화해 주었다.

graph = [[list(map(int, input().split())) for _ in range (N)] for _ in range(H)]
visited = [[[-1] * M for _ in range(N)] for _ in range(H)]

[[[M개의 길이를 가진 리스트] * N개] * M개]의 형태이다.

그 후 3중 for문을 돌면서 그래프에서 1인 칸(익은 토마토)을 찾아서 큐에 저장한다.

이 과정을 아래와 같이 하나의 과정으로 통합하신 분도 계셨다.

for i in range(h):
    tmp = []
    for j in range(n):
        tmp.append(list(map(int,sys.stdin.readline().split())))
        for k in range(m):
            if tmp[j][k]==1:
                queue.append([i,j,k])
    graph.append(tmp)

익은 토마토의 위치를 찾았다면 bfs를 수행하면 된다.

2차원 토마토와 같은 로직으로 탐색을 진행하면 되는데 이번 문제는 3차원이므로 dx, dy에 dz까지 추가한다.

상, 하, 좌, 우, 위, 아래로 이동해 보면서 이동한 그래프에 0(익지 않은 토마토)이 있다면

큐에 해당 칸을 추가하고 visited에 이전 칸 +1을 저장한다.

이후에 알게 된 사실인데 visited를 따로 관리하지 않고 graph를 바로 수정해도 풀이가 가능했다.

3. 코드

나의 코드:

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

M, N, H = map(int, input().split())
graph = [[list(map(int, input().split())) for _ in range (N)] for _ in range(H)]
visited = [[[-1] * M for _ in range(N)] for _ in range(H)]
queue = deque()

for i in range (H):
    for j in range (N):
        for k in range (M):
            if graph[i][j][k] == 1:
                queue.append((i,j,k))
                visited[i][j][k] = 0
    
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]

while queue:
    x, y, z = queue.popleft()
    
    for i in range (6):
        nx = x + dx[i]
        ny = y + dy[i]
        nz = z + dz[i]
        
        if 0 <= nx < H and 0 <= ny < N and 0 <= nz < M and visited[nx][ny][nz] == -1:
            if graph[nx][ny][nz] == 0:
                queue.append((nx,ny,nz))
                visited[nx][ny][nz] = visited[x][y][z]+1
                
for i in range (H):
    for j in range (N):
        for k in range (M):
            if graph[i][j][k] != -1 and visited[i][j][k] == -1:
                print(-1)
                exit(0)
max = 0
for i in range (H):
    for j in range (N):
        for k in range (M):
            if visited[i][j][k] > max:
                max = visited[i][j][k]
                
print(max)

다른 분의 코드:

import sys
from collections import deque
m,n,h = map(int,input().split()) # mn크기, h상자수
graph = []
queue = deque([])
 
for i in range(h):
    tmp = []
    for j in range(n):
        tmp.append(list(map(int,sys.stdin.readline().split())))
        for k in range(m):
            if tmp[j][k]==1:
                queue.append([i,j,k])
    graph.append(tmp)
    
dx = [-1,1,0,0,0,0]
dy = [0,0,1,-1,0,0]
dz = [0,0,0,0,1,-1]
while(queue):
    x,y,z = queue.popleft()
    
    for i in range(6):
        a = x+dx[i]
        b = y+dy[i]
        c = z+dz[i]
        if 0<=a<h and 0<=b<n and 0<=c<m and graph[a][b][c]==0:
            queue.append([a,b,c])
            graph[a][b][c] = graph[x][y][z]+1
            
day = 0
for i in graph:
    for j in i:
        for k in j:
            if k==0:
                print(-1)
                exit(0)
        day = max(day,max(j))
print(day-1)