백준 - 7569 토마토 (파이썬)

문제 링크 : https://www.acmicpc.net/problem/7576
난이도 : 골드 5

문제풀이

---

문제 정리

• 인접한 토마토는 익는다.
• 토마토 박스는 층층이 쌓여있어서 인접한 토마토는 동, 서, 남, 북, 위, 아래 총 6방향을 의미한다
• 며칠 쯤에 다 익을지 묻는 문제이다

분석

1. 토마토가 다 익는 최소일수를 묻는 문제이기 때문에 BFS를 사용하여야 한다.

2. 탐색 문제는 어려워질 수록 탐색에 간선에 조건이 달리는데, 여기서는 위, 아래가 추가 되었다.

3. 입력은 2차원으로 주어지는데, 문제는 삼차원이기 때문에 탐색 범위를 제한하는데 두 가지 방식이 있을 것이다.

   2차원 입력을 2차원 배열로 받는 경우

   • 높이에 관한 탐색 범위를 제한할 때, 가로 세로는 0 <= 다음 위치 < N 과 같은 방식으로 제한할 수 있으나 높이는 높이-1 <= 다음 높이 <= 높이+1 과 0 <= 다음 높이 < H 처럼 제한해야 하며 통일성을 유지하며 구현하기 힘들다.

     box = [list(map(int, input().split())) for _ in range(N*H)]

   2차원 입력을 3차원 배열(텐서)로 받는 경우

   • 다음 움직임을 통일성을 유지하며 움직이기 좋다.

     box = [[list(map(int, input().split())) for _ in range(N)] for _ in range(H)]
      dx, dy, dh = [-1, 0, 1, 0, 0, 0], [0, 1, 0, -1, 0, 0], [0, 0 ,0 ,0, 1, -1]
      .
      .
      for i in range(6):
               xx, yy, hh = x + dx[i], y + dy[i], h + dh[i]
               if xx >= 0 and xx < N and yy >= 0 and yy < M and hh >= 0 and hh < H:

4. 그 다음 토마토가 떨어져 존재하는 경우를 생각해볼 수 있다. 이런 경우를 대비해 토마토가 떨어져 존재하는 위치를 배열로 담아 초기 큐에 넣어 줄 수 있다.

   cand = deque([])
   for k in range(H):
     for i in range(N):
         for j in range(M):
             if box[k][i][j] == 1:
                cand.append([k,i,j])

시간복잡도

• BFS의 시간복잡도는 간선 + 노드의 수로 결정된다.
• 여기서는 간선(100만) + 노드 400만 = 600만 정도 된다.
• 충분히 여유있을거라 예상된다.

전체코드

---

from collections import deque

M, N, H = map(int, input().split())

box = [[list(map(int, input().split())) for _ in range(N)] for _ in range(H)]

# 상하 - N 만큼 + -
dx, dy, dh = [-1, 0, 1, 0, 0, 0], [0, 1, 0, -1, 0, 0], [0, 0 ,0 ,0, 1, -1]

def bfs(cand):

    queue = cand

    while queue:
        h, x, y = queue.popleft()
        
    
        for i in range(6):
            xx, yy, hh = x + dx[i], y + dy[i], h + dh[i]

            if xx >= 0 and xx < N and yy >= 0 and yy < M and hh >= 0 and hh < H:
                if box[hh][xx][yy] == 0:
                    box[hh][xx][yy] = box[h][x][y] + 1
                    queue.append([hh, xx, yy])

def check() :
    max_val = -1e9
    for k in range(H):
        for i in range(N):
            for j in range(M):
                if box[k][i][j] == 0:
                    return -1
                max_val = max(max_val, box[k][i][j])
    
    return max_val - 1
    
cand = deque([])
for k in range(H):
    for i in range(N):
        for j in range(M):
            if box[k][i][j] == 1:
               cand.append([k,i,j])
                
bfs(cand)
print(check())

정리 및 느낀점

---

• 토마토가 익는 최소일 수 BFS
• 떨어진 지점에서 동시에 BFS가 시작되어야 할 때 후보군을 만들어 초기 큐의 원소로 넘겨줘야한다