7569번: 토마토

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

 

3차원 배열에서의 BFS문제

 

기존에 defaultdict을 활용한 Graph를 중심으로 탐색을 진행했었는데, 이번엔 메모리 초과 문제로 사용을 포기했다.

대신 BOX와 visited를 적극 활용하여 defaultdict을 대신했다.

토마토가 다 익는데 필요한 시간은 visited에 적어 최대한 메모리 사용을 줄였다.

 

조건이 몇 개 있다. 토마토가 모두 익지 못하는 경우, 애초에 토마토가 모두 익어 있는 경우에 다른 수를 출력해야 한다.

이를 위해 green_tomatos라는 변수를 둬서 BFS 중 익을 경우 요소를 제거하는 방식으로 안 익은 토마토를 바로 확인할 수 있도록 했다.

또한 처음 BFS를 시작하기 전 green_tomatos의 요소 갯수가 0이라면, 애초에 토마토가 모두 익어 있는 경우이므로, 0을 출력하도록 했다.

 

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

import sys
from collections import deque, defaultdict

M, N, H = map(int, sys.stdin.readline().split())
red_tomatos = []
green_tomatos = set([])
BOX = []
for h in range(H) :
    MAP = []
    for n in range(N) :
        line = list(map(int, sys.stdin.readline().split()))
        for m, l in enumerate(line) :
            if l == 1 : # 익은 토마토
                red_tomatos.append((h, n, m))
            elif l == 0 :
                green_tomatos.add((h, n, m))
        MAP.append(line)
    BOX.append(MAP)

if len(green_tomatos) == 0 :
    print(0)
    
else :
    visited = [[[-1 for _ in range(M)] for _ in range(N)] for _ in range(H)]
    def BFS(start, visited, green_tomatos) :
        q = deque(start)
        for tomato in start :
            visited[tomato[0]][tomato[1]][tomato[2]] = 0
        
        ans = 0
        dx = [0, 0, -1, 1, 0, 0]
        dy = [-1, 1, 0, 0, 0, 0]
        dz = [0, 0, 0, 0, -1, 1]
        while q :
            h, n, m = q.popleft()
            new_day = visited[h][n][m] + 1
            for idx in range(6) :
                new_n = n + dx[idx]
                new_m = m + dy[idx]
                new_h = h + dz[idx]
                
                if new_n < 0 or new_n > (N-1) or new_m < 0 or new_m > (M-1) or new_h < 0 or new_h > (H-1) :
                    continue
                else :
                    if visited[new_h][new_n][new_m] == -1 and BOX[new_h][new_n][new_m] == 0 :
                        q.append((new_h, new_n, new_m))
                        visited[new_h][new_n][new_m] = new_day
                        if new_day > ans :
                            ans = new_day
                        green_tomatos.remove((new_h, new_n, new_m))
        if len(green_tomatos) == 0 :
            print(ans)
        else :
            print(-1)

    BFS(red_tomatos, visited, green_tomatos)