[백준/Gold5]7569. Tomato (python)

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

• 풀이 코드

  # https://www.acmicpc.net/problem/7569
  
  import sys, collections
  
  input = sys.stdin.readline
  
  # 가로(열), 세로(행), 높이
  N, M, H = map(int, input().split(" "))
  
  arr = []
  subArr = []
  
  for i in range(M * H):
    if i % M == 0 and subArr:
      arr.append(subArr[:])
      subArr = []
  
    subArr.append(list(map(int, input().split(" "))))
  
  arr.append(subArr[:])
  
  dh = [0, 0, 0, 0, 1, -1]
  dr = [1, -1, 0, 0, 0, 0]
  dc = [0, 0, 1, -1, 0, 0]
  
  def check_days():
  
    while q:
      (h, r, c) = q.popleft()
      days = arr[h][r][c]
  
      for i in range(6):
        nh, nr, nc = h + dh[i], r + dr[i], c + dc[i]
  
        if nh < 0 or nh > H -1 or nr < 0 or nr > M -1 or nc < 0 or nc > N -1:
          continue 
  
        # bfs 특성상 후자의 조건에 걸릴 가능성은 없을 거 같긴 함
        if arr[nh][nr][nc] == 0 or arr[nh][nr][nc] > days + 1: 
          arr[nh][nr][nc] = days + 1
  
          q.append((nh, nr, nc))
  
  q = collections.deque()
  
  for i in range(H):
    for j in range(M):
      for k in range(N):
  
        if arr[i][j][k] == 1:
            # 멀티 소스 bfs
            # 이 부분!!! 풀이 보고 해결, 처음부터 익은 토마토들을 큐에 넣고 bfs 돌려야 했음
          q.append((i, j, k))
  
  check_days()
  
  result = 0
  flag = False
  
  for i in range(H):
    for j in range(M):
      for k in range(N):
        if arr[i][j][k] == 0:
          flag = True
          break
        result = max(result, arr[i][j][k])
  
  print(result - 1 if not flag else -1)

• 3차원 배열 bfs 는 처음 풀어보는 거 같다.

• 멀티 소스 bfs 도 처음이다.

  • 그러다보니 멀티 소스 bfs 풀이를 바로 생각해내지 못했다. 처음에는 시간초과가 났다. 그래서 풀이를 살짝 찾아보고 수정한 건 안 비밀..!
  • 변명?이지만 그 부분을 빼곤 기본 탐색 로직은 금방 작성했다...!