백준 7569번 토마토
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 99932 | 43457 | 31876 | 42.746% |
문제
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
[입력]
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
[출력]
여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
문제 해석하기
익는데 걸리는 최소 일수와 인접한 토마토라는 내용을 봤을때 딱 BFS를 사용해야 하는 문제구나 라는 걸 알 수 있었다.
⇒ 이를 이용해서 3차원 배열로 만든 공간에서 BFS탐색을 적용하고자했다.
(dx,dy,dz)를 적용해서 탐색을 시도한다.
- 일단, BFS문제이기 때문에 deque를 import해준다.
- 가로, 세로, 높이를 map을 이용해서 받아준다.
- 토마토가 들어갈 box를 만들어준다.
- 높이만큼 한 층의 레이어를 쌓아준다는 생각으로 리스트 형태를 통해 값을 받아주고 이를 높이만큼 반복하여 구성해준다.
- dx,dy,dz를 만들어주어 상하좌우앞뒤로 이동할 수 있도록 해준다.
- bfs를 사용하기 위해서 큐를 초기화해준다.
- 토마토의 위치를 큐에 append해주어 후에 bfs를 사용하면서 해당하는 토마토와 인접한 장소를 찾을 수 있도록 해준다.
- bfs 함수 생성
- 큐에서 토마토의 위치를 일단 popleft하여 해당 토마토의 인접한 곳을 탐색하도록 한다.
- queue가 존재하는 동안 그래프를 돌리고, 총 6방향을 탐색하도록 한다.
- 방향을 이동하면서 벗어나는 곳이나, 익지 않은 토마토인지 확인하면서 큐에 추가하도록 한다.
- 모든 토마토가 익었는지 확인하기 위해서 변수들을 생성해주고,
- BFS가 종료된 후, tomato_box를 순회하며 모든 토마토가 익었는지 확인한다
- 익지 않은 토마토가 있다면 all_ripe를 False로 설정하고, 모든 토마토가 익지 않았으므로 1을 출력한다.
- 모든 토마토가 익었다면, 최대 일수를 계산하여 출력한다.
from collections import deque
m, n, h = map(int, input().split()) # 가로, 세로, 높이
tomato_box = []
for _ in range(h):
layer = [list(map(int, input().split())) for _ in range(n)]
tomato_box.append(layer)
# 방향 벡터 정의
dz = [-1, 1, 0, 0, 0, 0]
dx = [0, 0, -1, 1, 0, 0]
dy = [0, 0, 0, 0, -1, 1]
queue = deque()
# 익은 토마토의 위치를 큐에 추가
for z in range(h):
for x in range(n):
for y in range(m):
if tomato_box[z][x][y] == 1: # 익은 토마토
queue.append((z, x, y))
def bfs():
while queue:
z, x, y = queue.popleft()
for i in range(6): # 6방향 탐색
nz, nx, ny = z + dz[i], x + dx[i], y + dy[i]
# 범위를 벗어나지 않는지, 그리고 익지 않은 토마토(0)인지 확인
if 0 <= nz < h and 0 <= nx < n and 0 <= ny < m and tomato_box[nz][nx][ny] == 0:
tomato_box[nz][nx][ny] = tomato_box[z][x][y] + 1
queue.append((nz, nx, ny))
bfs()
# 모든 토마토가 익었는지 확인 및 최대 일수 계산
max_days = 0
all_ripe = True
for z in range(h):
for x in range(n):
for y in range(m):
if tomato_box[z][x][y] == 0: # 익지 않은 토마토가 남아 있는 경우
all_ripe = False
max_days = max(max_days, tomato_box[z][x][y])
# 결과 출력
if not all_ripe:
print(-1)
else:
print(max_days - 1) # 첫 날이 1로 시작했으므로 -1 해서 일수 계산
오늘의 회고
dx, dy를 사용하는 문제는 풀어본 적이 있는데, dz까지 사용해본 건 처음이라 조금 생소했던 문제였다. 2차원 배열을 생성하는 것도 어려운데 3차원 배열이라니....좀 더 열심히 공부해서 3차원 배열도 쉽게 풀 수 있는 사람이 되어야겠다..
