[BOJ] 7569 토마토 바로가기
📍 문제
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
📍 입력
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
📍 출력
여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
📍 풀이
💡 고찰
- 그래스 파이어(
Grass Fire) 알고리즘을 이용하여 문제를 해결하였다.- BFS 알고리즘과 큰 차이는 없다.
- 익지 않은 토마토(
0)는chain()함수를 이용하여 개수를 셀 수 있었다. chain()함수는 iterable한 객체를 인수로 받아 하나의 iterator로 변환해 준다.
📌 문제 풀이
✏️ 1. 익지 않은 토마토의 개수 세기
rawTomatoes = list(chain(*list(chain(*box)))).count(0) - 3차원 리스트이므로
chain()함수를 2번 적용하여 1차원 리스트로 변경한다. - 변경된 1차원 리스트에서
count()함수를 이용하여 익지 않은 토마토(0)의 개수를 센다.
✏️ 2. 익은 토마토의 위치 찾기
startPoints = set()
for z in range(H):
for y in range(N):
for x in range(M):
if box[z][y][x] == 1:
startPoints.add((x,y,z))- Grass Fire 알고리즘을 적용하기 위해 익은 토마토의 위치를 찾는다.
✏️ 3. 익게될 토마토의 위치 찾기
newPoints = set()
for x, y, z in startPoints:
for dx, dy, dz in ((1,0,0),(-1,0,0),(0,1,0),(0,-1,0),(0,0,1),(0,0,-1)):
nx, ny, nz = x + dx, y + dy, z + dz
if nx < 0 or nx >= M or ny < 0 or ny >= N or nz < 0 or nz >= H or box[nz][ny][nx] != 0: continue
newPoints.add((nx,ny,nz))
if not newPoints:
break
for x, y, z in newPoints:
box[z][y][x] = 1
rawTomatoes -= 1
startPoints = newPoints
answer += 1- 익게될 토마토의 위치를 저장할 집합 자료구조(
newPoints)) 생성 - 익은 토마토의 위치(
startPoints)의 상하좌우앞뒤를 탐색하여 익게될 토마토의 위치를 저장 - 탐색이 종료된 후 새로 익게될 토마토가 존재하지 않는다면 반복문 종료
- 탐색이 종료된 후 새로 익게될 토마토가 존재한다면 익게될 토마토값
1로 변경, 익지 않은 토마토의 개수(rawTomatoes)1감소 - 익은 토마토가 존재하는 지점(
startPoint)을 익게될 토마토가 존재하는 지점(newPoints)로 갱신 - 토마토들이 모두 익는 최소 일수(
answer)1증가
✏️ 4. 결과 반환
if rawTomatoes != 0:
return - 1
# 모든 토마토가 익었다면
else:
return answer- 만약 모든 토마토가 익지 않았다면 즉, 익지 않은 토마토의 개수가
0이 아니라면-1반환 - 모든 토마토가 익었다면 토마토들이 모두 익는 최소 일수(
answer) 반환
✍ 코드
from sys import stdin
from itertools import chain
def solution(M, N, H, box):
# 토마토들이 모두 익는 최소 일수
answer = 0
# 익지 않은 토마토의 개수
rawTomatoes = list(chain(*list(chain(*box)))).count(0)
# 익은 토마토가 존재하는 지점
startPoints = set()
for z in range(H):
for y in range(N):
for x in range(M):
if box[z][y][x] == 1:
startPoints.add((x,y,z))
while True:
# 익게될 토마토가 존재하는 지점
newPoints = set()
# 익은 토마토가 존재하는 지점(startPoint)를 기준으로 여섯 방향 탐색
for x, y, z in startPoints:
for dx, dy, dz in ((1,0,0),(-1,0,0),(0,1,0),(0,-1,0),(0,0,1),(0,0,-1)):
nx, ny, nz = x + dx, y + dy, z + dz
if nx < 0 or nx >= M or ny < 0 or ny >= N or nz < 0 or nz >= H or box[nz][ny][nx] != 0: continue
newPoints.add((nx,ny,nz))
# 익게될 토마토가 존재하지 않는다면
if not newPoints:
break
# 토마토 익는중...
for x, y, z in newPoints:
box[z][y][x] = 1
rawTomatoes -= 1
# 익은 토마토가 존재하는 지점(startPoint)을 익게될 토마토가 존재하는 지점(newPoints)로 갱신
startPoints = newPoints
# 토마토들이 모두 익는 최소 일수 1 증가
answer += 1
# 만약 모든 토마토가 익지 않았다면
if rawTomatoes != 0:
return - 1
# 모든 토마토가 익었다면
else:
return answer
# input
M, N, H = map(int,stdin.readline().split()) # 가로, 세로, 높이
box = [ list(list(map(int,stdin.readline().split())) for _ in range(N)) for _ in range(H) ]
# result
result = solution(M, N, H, box)
print(result)