[백준/python][BFS] 7569번 토마토 - 3차원

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

7569번: 토마토

 

# 문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

---

# 입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M, N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

---

# 출력

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

---

# 코드

import sys
from collections import deque

r_line = sys.stdin.readline
move = [(-1,0,0), (1,0,0), (0,-1,0), (0,1,0), (0,0,-1), (0,0,1)] # 상하좌우위아래
que = deque()

def bfs():    
    while que:
        z, x, y = que.popleft()
        for dx,dy,dz in move:
            px = x + dx
            py = y + dy
            pz = z + dz
            # 이동가능하고 익지않은 토마토라면
            if 0<=px<N and 0<=py<M and 0<=pz<H and mat[pz][px][py] == 0:
                mat[pz][px][py] = mat[z][x][y]+1
                que.append((pz,px,py))

# M:열, N:행
M, N, H = map(int, r_line().split())
mat = [[[0]*M for _ in range(N)] for _ in range(H)]

# 입력
for i in range(H):
   for j in range(N): 
        mat[i][j] = list(map(int, r_line().split()))
        

for i in range(H): # 박스
    for j in range(N): # 행 
        for k in range(M): # 열
                if mat[i][j][k] == 1: # 익은 토마토라면 
                    que.append((i,j,k))
                    
bfs()

# 익지않은 토마토있으면 실패
flag = 0
days = 0
for i in range(H): # 박스
        for j in range(N): # 행 
            for k in range(M): # 열
                if mat[i][j][k] == 0:
                    flag = 1
                days = max(days, mat[i][j][k])
                
for i in range(H):
    for j in range(N): 
        print(mat[i][j])

if flag == 1:
    days = 0
print(days-1)

 

---

# 풀이

3차원일때, 1개의 차원을 더추가해서

move = [(-1,0,0), (1,0,0), (0,-1,0), (0,1,0), (0,0,-1), (0,0,1)] # 상하좌우위아래

 

라고 할 수 있다.

for dx,dy,dz in move:
            px = x + dx
            py = y + dy
            pz = z + dz

 

그리고 이렇게 6번 돌며, 검사가 가능하다.

 

익은 토마토 -> 익지 않은 토마토

로 나아가며 나아갈 때 익은 토마토 +1의 값을 전파합니다.

이렇게 days(탐색의 횟수)를 tabulation방식으로 저장해 나가면

방문여부를 표시하는 별도의 visited리스트 관리 없이 탐색 횟수를 저장할 수 있습니다.

 

매트리스(mat)의 저장된 최댓값이 탐색 횟수와 같게 됩니다.

 

예제 2번의 출력 예시입니다.

 

# 시간초과풀이

import sys
import copy

move = [(-1,0),(1,0),(0,-1),(0,1)] # 상하좌우
move_box = [1, -1] # 위 아래  

def bfs(box, x, y):    
    spread_cnt = 0 # 변화량
    
    # 1) 상하좌우
    for dx, dy in move:
        px = x + dx
        py = y + dy
        
        # 이동가능하고 익지않은 토마토라면
        if 0<=px<N and 0<=py<M and mat[box][px][py] == 0:
            copied_mat[box][px][py] = 1 # 익은 토마토 진화.
            spread_cnt += 1 # 변화량
            
    # 2) 위아래
    for up_down in move_box:
        p_box = box + up_down
        
        # 박스이동가능하고 익지않은 토마토라면
        if 0<=p_box<H and mat[p_box][x][y] == 0: 
            copied_mat[p_box][x][y] = 1 # 익은 토마토 진화.
            spread_cnt += 1 # 변화량
    return spread_cnt
            
r_line = sys.stdin.readline

# M:열, N:행
M, N, H = map(int, r_line().split())

mat = [[[0]*M for _ in range(N)] for _ in range(H)]

# 입력
for i in range(H):
   for j in range(N): 
        mat[i][j] = list(map(int, r_line().split()))
        

# 비즈니스 로직
copied_mat = copy.deepcopy(mat)

days = 0
nowadays_cnt = 0
while True:
    for i in range(H): # 박스
        for j in range(N): # 행 
            for k in range(M): # 열
                    if mat[i][j][k] == 1: # 익은 토마토라면 
                        nowadays_cnt += bfs(i, j, k) # 토마토 퍼져나가기
                        
    # 종료조건.
    # 1) 모두 익거나
    # 2) 불가능일때 == 하루 변화량이 0 일때
    if nowadays_cnt == 0: 
        break # 탈출
    nowadays_cnt = 0
    days += 1 # 하루증가.
    mat = copy.deepcopy(copied_mat) # mat에게 복사.

# 다같이 spread
# 익지않은 토마토있으면 실패
flag = 0
for i in range(H): # 박스
        for j in range(N): # 행 
            for k in range(M): # 열
                if mat[i][j][k] == 0:
                    flag = 1

if flag == 1:
    days = -1
    
print(days)
                
for i in range(H):
    for j in range(N): 
        print(mat[i][j])

이 풀이는 정답은 나오지만 시간이 초과하여 실패한 풀이입니다.

 

맞은풀이는 (pypy, python3) 2개로 체점해봄.

 

<시간초과의 이유>

1)

visited가 없어서 계속 반복하며 익은 토마토가 있다면 무조건 검사를 진행했음.

(예를 들어 1번째 날에 검사한 익은 토마토는 2번째 날부터 검사할 필요 없는데 또 검사한 거임)

==> 방문처리가 안되어있음.

2)
배열을 2개 만들었음

하루가 끝날 때마다 배열을 전부 deepcopy 함. (최대 100만 번의 연산발생, 100x100x100)

 

---

#피드백 (시간초과코드 vs 성공한 코드)

방문처리를 하지 않으면 

들렸던 곳을 또 들리기에 mat가 커질 경우, 필요 없는(불필요한) 연산이 지속됨. => 시간초과의 원인

그에 반해,

성공코드는 방문한 곳은 철저하게 다시 방문하지 않음.

또한 해당 mat에 방문처리를 섞어서 추가적인 방문알고리즘 발생하지 않았음.