백준7569 - 토마토 (BFS) Python

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

해당 문제는 X,Y,Z의 길이와 토마토의 정보가 주어진다. 이때 정수 1은 익은 토마토, 0은 익지 않은 토마토, -1 은 토마토가 들어있지 않은 칸이라고 하고, 익은 토마토는 상, 하, 좌, 우, 앞, 뒤에 익지 않은 토마토를 하루 후에 익게 만든다고 할 때 전체 토마토가 다 익기까지 얼마나 걸리는지 구하는 문제다.

 

문제 해결 방식

익은 토마토가 상하좌우 뿐만 아니라 앞뒤로도 이동하며 다른 토마토를 익게 하기 때문에, 3차원 배열로 문제를 해결했다.

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()
from collections import deque

def solution (data) :
  arr = [list(map(int, v.split())) for v in data]
  X,Y,Z = arr.pop(0)
  matrix = []
  for i in range(0,len(arr),Y) :
    matrix.append(arr[i:i+Y])
  
  start = []
  zeroCnt = 0
  for i in range(Z) :
    for j in range(Y) :
      for k in range(X) :
        if matrix[i][j][k] == 1 : 
          start.append((1,i,j,k)) # 익은 토마토를 배열에 담음 
        if matrix[i][j][k] == 0 :
          zeroCnt += 1
  
  def verify (z,y,x) : # 상하좌우앞뒤 좌표 검증
    return 0 <= x < X and 0 <= y < Y and 0 <= z < Z
    
  def BFS () :
    queue = deque([*start])
    directions = [[0,0,-1],[0,0,1],[0,-1,0],[0,1,0],[-1,0,0],[1,0,0]]
    visited = [[[False for _ in range(X)] for _ in range(Y)] for _ in range(Z)]
    
    while queue :
      dist,z,y,x = queue.popleft()
      if visited[z][y][x] : continue
      matrix[z][y][x] = dist
      visited[z][y][x] = True
      
      for dz, dy, dx in directions :
        nz, ny, nx = dz + z, dy + y, dx + x
        if verify(nz,ny,nx) and matrix[nz][ny][nx] == 0 and not visited[nz][ny][nx] :
          queue.append((dist+1,nz,ny,nx))
  
  if zeroCnt == 0 :
    print(0)
    return
  
  BFS() # BFS 알고리즘 실행
  
  def matrixVerify () : # matrix 검증
    maxValue = 0 # 가장 오래걸린 날짜가 기록될 변수
    for i in range(Z) : 
      for j in range(Y) :
        for k in range(X) :
          if matrix[i][j][k] == 0 : return -1 # 익지 않은 토마토가 존재한다면 -1 반환
          maxValue = max(maxValue, matrix[i][j][k])
    return maxValue - 1
    
  result = matrixVerify()
  print(result)
    
solution(input_data)