토마토 (7569)

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

 

나의 풀이

from collections import deque
import sys
input = sys.stdin.readline

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

def result_check(floor_dict, ct):
    for fk in floor_dict.keys():
        for i in range(N):
            for j in range(M):
                if floor_dict[fk][i][j] == 0:
                    return -1
    return ct
    
floor_dict = {}
queue = deque()
for i in range(H):
    n_list = []
    for j in range(N):
        n_list.append(list(map(int, input().rstrip().split())))
        
        for idx in range(M):
            if n_list[j][idx] == 1:
                queue.append((i, j, idx))
    floor_dict[i] = n_list

# 탐색 시작
ct = 0
while queue:
    next_queue = deque()
    
    while queue:
        i, a, b = queue.popleft()
        for m_a, m_b in ((1,0),(-1,0),(0,1),(0,-1)):
            n_a, n_b = a+m_a, b+m_b
            if (0 <= n_a < N) and (0 <= n_b < M) and (floor_dict[i][n_a][n_b] == 0):
                floor_dict[i][n_a][n_b] = 1
                next_queue.append((i, n_a, n_b))
        for m_h in (1,-1):
            n_h = i+m_h
            if (0 <= n_h < H) and (floor_dict[n_h][a][b] == 0):
                floor_dict[n_h][a][b] = 1
                next_queue.append((n_h, a, b))

    if next_queue:
        ct += 1
        queue = next_queue
    else:
        break

print(result_check(floor_dict, ct))

 

시간 복잡도

3차원의 BFS를 탐색 하므로 ( 삼차형 시간 복잡도 )
해당 알고리즘 시간 복잡도는 : 삼차형 시간 복잡도 ( O(n**3) )