python 백준 7569번 토마토

목표 : 이미 익은 숫자 '1'인 토마토가 아직 익지 않은 숫자'0'인 토마토를 모두 익히는데 까지 걸리는 최소시간을 구하시오

 

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

7569번: 토마토

 

import sys
## bfs queue 방식을 이용하기 위해 pop(0)보다 빠른 deque -> popleft를 사용
from collections import deque

## 가로 세로 높이 3차원 배열 크기 ##
m,n,h = map(int,sys.stdin.readline().split())
matrix = []
for i in range(h):
    temp = []
    for j in range(n):
        temp.append(list(map(int,sys.stdin.readline().split())))
    matrix.append(temp)
## 비정상적으로 서치가 끝났는지 확인 ##
stable = False
## count 총 토마토의 개수, check_count 0->1로 변한 토마토의 개수, zero_count 초기 익지않은 토마토의 개수##
count = 0
check_count = 0
zero_count = 0
one_lo = []
maximum = 0
## 매트릭스를 서치하여 0,1,-1의 개수를 파악##
for q in range(h):
    for w in range(n):
        for e in range(m):
            if matrix[q][w][e] == 1:
                one_lo.append([q,w,e])
            if matrix[q][w][e] >= 0:
                count += 1
            if matrix[q][w][e] == 0:
                zero_count += 1

## bfs 너비우선 탐색을 사용 ##
## bfs를 통해 선입선출이 가능해져 dfs와 다르게 주변값들을 전부 훓으면서 갈 수 있음 ##
## 자식노드와 연결되있는 하위 노드들이 뒤로 쌓이고 pop이 앞에서 되기때문이다 ##
def bfs(one_lo):
    global maximum,check_count
    queue = deque()
## 공간관련 문제에서 상하좌우 이상을 체크할때 주로 사용됨 ##
    dx = [1,-1,0,0,0,0]
    dy = [0,0,1,-1,0,0]
    dz = [0,0,0,0,1,-1]
## 익은 토마토가 여러개인 경우 동시에 주변 토마토들에게 영향을 주기 때문에 queue개념을 사용 ##
## 1의 위치값을 전부 저장함 ##
    for asd in one_lo:
        queue.append(asd)
    while queue:
        z,y,x = queue.popleft()
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
            if nx < 0 or nx>=m or ny<0 or ny>=n or nz<0 or nz>=h:
                continue
            if matrix[nz][ny][nx] == -1:
                continue
            elif matrix[nz][ny][nx] > 0:
                continue
            elif matrix[nz][ny][nx] == 0:
                check_count += 1
                queue.append((nz,ny,nx))
## 날짜,시간 계산 코드 bfs이기 때문에 본인에 인접한 vertex를 탐색함으로써 주변만 +1 을 시켜줌 ##
                matrix[nz][ny][nx] = matrix[z][y][x] + 1
                if matrix[z][y][x] + 1 > maximum:
                    maximum = matrix[z][y][x] + 1


if zero_count == 0 and count>0:
    stable = True
    print(0)
elif stable == False:            
    bfs(one_lo)
## 이니셜 0의 개수가 == 1로 변한 토마토의 개수가 같으면 모든 0 -> 1로 바꾼거와 같다. ##
    if check_count == zero_count and count>0:
        print(maximum-1)
    else:
        print(-1)