[백준_7569]토마토_python

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

7569번: 토마토

문제

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

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

출력

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

문제 해결

이와 비슷한 7576의 토마토 문제는 2차원에서의 bfs문제였다면 이 문제는 3차원이다. 3차원이란 걸 알고 두려움이 앞서 풀지 않고 1주일이 지난 지금 문제를 다시 보니 생각보다 풀만했다.! dx, dy테크닉을 활용하면 보통 상하좌우인 경우를 많이 구현하였는데 이 문제는 앞, 뒤까지 구현해야 한다. 여기서 겁먹지 않으면 문제는 다 풀린 거다. 대각선이동이 없으니 dz(3차원의 입체부분)배열을 만들어 현재위치에서 앞뒤(1,-1)만 체크해주면 문제는 다 풀린거다. 

너비 우선 탐색, 숫자를 찾는 함수, 범위 체크 함수 정도를 함수로 설정하였고 3차원 그래프를 탐색하며 1이 되는 부분을

우선 q에 넣어 bfs를 실행해주었다.

import sys
input = sys.stdin.readline
from collections import deque
q = deque()
n,m,h = map(int,input().split())#열,행,높이
graph = []
cnt = 0
for _ in range(h) :
    s = [list(map(int,input().split())) for _ in range(m)]
    graph.append(s)
dx,dy,dh = [1,-1,0,0,0,0],[0,0,1,-1,0,0],[0,0,0,0,1,-1]
def bfs():
    global cnt
    while q:
        cnt += 1
        for _ in range(len(q)):
            z,x,y = q.popleft() #높이,행.열 #현재위치
            for i in range(6):
                nz, nx, ny = dh[i]+z, dx[i]+x, dy[i]+y
                if in_range(nx,ny,nz):
                    if graph[nz][nx][ny] == 0:
                        graph[nz][nx][ny] = 1
                        q.append((nz,nx,ny))

def check(x):   #x숫자가 있는지 찾기
    for t in range(h):
        for i in range(m):
            for j in range(n):
                if graph[t][i][j] == x:
                    return True
    return False

def in_range(x,y,height):#행,열,높이
    return 0<=x<m and 0<=y<n and 0<=height<h

for t in range(h):#높이
    for i in range(m):#행
        for j in range(n):#열
            if graph[t][i][j] == 1:#1,5,3
                q.append((t,i,j))   #시작위치를 넣어주고#높이,행,열


if not check(0):
    print(0)
    exit(0)
bfs()
if check(0):
    print(-1)
    exit(0)
print(cnt-1)