문제 이해
위와 같은 상자에 토마토들이 들어 있다!
익은 토마토가 들어있다면 1 비어있다면 -1, 안익은 토마토가 있다면 0을 입력으로 받는다.
안익은 토마토들은 익은 토마토가 인접해 있을 때 하루가 지나면 익게된다.
인접해있다는 기준은 상하좌우앞뒤이다.
며칠이 지나면 모든 토마토들이 다 익게될지를 구하는 문제이다.
토마토가 모두 익지 못하는 상황이면 -1을 출력하고 처음부터 익어있다면 0을 출력, 그 외에는 최소 며칠이 걸려 익게되는지를 출력해야한다.
문제 접근
우선 3차원으로 상하좌우앞뒤를 다루고 있기 때문에 전형적인 BFS문제라고 생각했다. 조금 다른 점은 3차원으로 되어있다는 것이다.
하지만 3차원이어도 결국 리스트에 넣고 인덱스만 잘 맞춰준다면 이차원 배열과 크게 다를바는 없었다!@!
따라서 아래와 같이 3가지 단계로 나누었다.
- 3차원의 이해
- BFS로 토마토를 익게하기
- 그에 며칠이 걸렸는지를 확인하기
문제 풀이
3차원의 이해
3차원으로 N,M,H를 받는데 H가 높이이기 때문에 첫번째 인덱스이고, 그 다음이 M, 그 다음이 N순이있다.
BFS를 위해서 dx, dy, dz를 설정해준다.
N, M, H = map(int, sys.stdin.readline().split())
box = [] # 3차원 H, M, N
for i in range(H):
pan = []
for j in range(M):
pan.append(list(map(int, sys.stdin.readline().split())))
box.append(pan)
dx = [0,0,-1,1,0,0] # 상하좌우앞뒤
dy = [1,-1,0,0,0,0]
dz = [0,0,0,0,-1,1]
BFS로 토마토를 익게하기
우선 초기에 입력으로 받았을 때의 익은 토마토의 좌표를 q에 넣어둔다. 이 때 마지막의 0은 세대를 나타내는것이다. 입력으로 받았기 때문에 세대는 0세대가 되는것이다.
이제 BFS를 설계해야한다.
사실 BFS는 2차원과 동일하게 설계해주면 된다. q를 popleft를 통해 값을 받아내고 이를 상,하,좌,우,앞,뒤를 확인하면서 조건에 부합한다면 이를 q에 다시 추가해주면된다. 그러면서 나는 box의 토마토를 1로 바꾸어주었다.
q = deque()
for i in range(H):
for j in range(M):
for k in range(N):
if box[i][j][k]==1:
q.append((i,j,k,0))
age = []
def bfs():
while q:
x,y,z,count = q.popleft()
age.append(count+1) # 세대 1 증가시키고 넣어주기
for i in range(6):
nx = x + dx[i] # 좌표 이동
ny = y + dy[i]
nz = z + dz[i]
if nx<0 or ny<0 or nz<0 or nx>=H or ny>=M or nz>=N: # 인덱스가 범위를 벗어난다면
continue
if box[nx][ny][nz]==0: # 익지않은 토마토라면
box[nx][ny][nz] = 1 # 익히고
q.append((nx,ny,nz,count+1)) # q에 추가해주기그에 며칠이 걸렸는지를 확인하기
아까 BFS에서 세대를 추가해주었는데, 이 세대들을 전부 넣어둔 age라는 리스트가 있다. 이 리스트의 가장 큰 값이 가장 마지막에 익은 토마토가 익기까지 걸린 시간이다. 따라서 max(age)를 확인하면된다.
하지만 처음 조건에서 익지 않은 토마토가 있다면 -1을 출력해야하기 때문에 아래와 같이 flag를 설정하여 익지 않은 토마토가 있다면 -1을 출력하도록 해주었다.
flag = True # 깃발, 익지 않은 토마토가 있다면 False로 바뀜
for i in range(H):
for j in range(M):
for k in range(N):
if box[i][j][k]==0:
flag = False
if flag==False: # 익지 않은 토마토가 있다면?
print(-1)
else: # 없다면 세대들 중에서 가장 높은 세대를 출력
print(max(age)-1)제출 코드
import sys
from collections import deque
N, M, H = map(int, sys.stdin.readline().split())
box = [] # 3차원 H, M, N
for i in range(H):
pan = []
for j in range(M):
pan.append(list(map(int, sys.stdin.readline().split())))
box.append(pan)
dx = [0,0,-1,1,0,0] # 상하좌우앞뒤
dy = [1,-1,0,0,0,0]
dz = [0,0,0,0,-1,1]
q = deque()
for i in range(H):
for j in range(M):
for k in range(N):
if box[i][j][k]==1:
q.append((i,j,k,0))
age = []
def bfs():
while q:
x,y,z,count = q.popleft()
age.append(count+1) # 세대 1 증가시키고 넣어주기
for i in range(6):
nx = x + dx[i] # 좌표 이동
ny = y + dy[i]
nz = z + dz[i]
if nx<0 or ny<0 or nz<0 or nx>=H or ny>=M or nz>=N: # 인덱스가 범위를 벗어난다면
continue
if box[nx][ny][nz]==0: # 익지않은 토마토라면
box[nx][ny][nz] = 1 # 익히고
q.append((nx,ny,nz,count+1)) # q에 추가해주기
bfs()
flag = True # 깃발, 익지 않은 토마토가 있다면 False로 바뀜
for i in range(H):
for j in range(M):
for k in range(N):
if box[i][j][k]==0:
flag = False
if flag==False: # 익지 않은 토마토가 있다면?
print(-1)
else: # 없다면 세대들 중에서 가장 높은 세대를 출력
print(max(age)-1)