백준 7569 토마토 3차원 BFS (파이썬)

아이디어

1. 전에 풀었던 7576 토마토 문제의 연장이다.
2. 토마토를 받을 배열과 visited를 3차원으로 변경하고 BFS를 돌려보자

 

---

풀이

import sys; from collections import deque

def bfs(H, N, M):
    for h in range(H):
        for i in range(N):
            for j in range(M):
                if tomato[h][i][j] == 1:
                    Q.append((h, i, j))
                    visited[h][i][j] = 1
    while Q:
        h, i, j = Q.popleft()
        '''
        3차원 리스트에서의 움직임의 델타를 추가하면 된다.
        2차원의 델타가 [1, 0].. 이었다면, 
        3차원은 [1, 0, 0], [0, 0, 1]... 등으로 주면 된다.
        '''
        for dh, di, dj in [[1, 0, 0], [0, 0, 1], [-1, 0, 0], [0, 0, -1], [0, 1, 0], [0, -1, 0]]:
            nh, nr, nc = h + dh, i + di, j + dj
            if 0 <= nh < H and 0 <= nr < N and 0 <= nc < M:
                if tomato[nh][nr][nc] == 0 and visited[nh][nr][nc] == 0:
                    Q.append((nh, nr, nc))
                    visited[nh][nr][nc] = visited[h][i][j] + 1

def result():
    for h in range(H):
        for i in range(N):
            for j in range(M):
                if tomato[h][i][j] == 0:
                    if visited[h][i][j] == 0:
                        return print(-1)
    ret = 0
    for h in range(H):
        for i in range(N):
            if max(visited[h][i]) > ret:
                ret = max(visited[h][i])
    return print(ret-1)

M, N, H = map(int, sys.stdin.readline().split())

tomato = [[list(map(int, sys.stdin.readline().split())) for _ in range(N)] for h in range(H)]

Q = deque()

visited = [[[0] * M for _ in range(N)]for h in range(H)]

bfs(H, N, M)

result()

 

---

해설 및 후기

1. 문제 풀이의 핵심은 3차원의 델타를 어떻게 주느냐 였다.
2. 이 부분에서 많이 헤매었는데, 기존 델타의 방향을 하나 더 추가해야 했다.
3. 기존 델타가 [0, 1] 이런 식이라면 3차원은 [0, 0, 1] 이런 식으로 하나 더 추가하면 되었다.
4. 일단 풀긴 풀었지만, 토마토가 익지 않은 경우를 찾는데 더 효율적인 방법으로 풀고 싶었다...
5. 다음부턴 더 효율적이고 최적화하여 풀어보기로 한다.