[백준/python][BFS] 7569번 토마토 - 3차원
https://www.acmicpc.net/problem/7569
7569번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,
www.acmicpc.net
# 문제
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
# 입력
첫 줄에는 상자의 크기를 나타내는 두 정수 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])이 풀이는 정답은 나오지만 시간이 초과하여 실패한 풀이입니다.
<시간초과의 이유>
1)
visited가 없어서 계속 반복하며 익은 토마토가 있다면 무조건 검사를 진행했음.
(예를 들어 1번째 날에 검사한 익은 토마토는 2번째 날부터 검사할 필요 없는데 또 검사한 거임)
==> 방문처리가 안되어있음.
2)
배열을 2개 만들었음
하루가 끝날 때마다 배열을 전부 deepcopy 함. (최대 100만 번의 연산발생, 100x100x100)
#피드백 (시간초과코드 vs 성공한 코드)
방문처리를 하지 않으면
들렸던 곳을 또 들리기에 mat가 커질 경우, 필요 없는(불필요한) 연산이 지속됨. => 시간초과의 원인
그에 반해,
성공코드는 방문한 곳은 철저하게 다시 방문하지 않음.
또한 해당 mat에 방문처리를 섞어서 추가적인 방문알고리즘 발생하지 않았음.