[Python] 7569번 토마토

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

7569번: 토마토

---

 

22/09/30

 

 

이 문제는 7576번 토마토와 거의 유사한 문제로, 이 문제에서 3차원으로 바꾸기만 하면 되는 문제이다.

 

https://lighter.tistory.com/34

[Python] 7576번 토마토

---

 

문제 접근 방식:

 

 

문제 접근 방식 자체는 위에서 올린 링크와 같다.

 

단지 다른 점은 3차원이기 때문에 그래프 입력도 3차원 리스트, BFS도 4방향이 아니라 6방향, 이중 for문이 아니라 3중 for문을 사용했다는 점이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 7569번 토마토
# 그래프 이론, 그래프 탐색, BFS
import sys
input = sys.stdin.readline
from collections import deque

M, N, H = map(int, input().rstrip().split())
graph = [[list(map(int, input().rstrip().split())) for _ in range(N)] for _ in range(H)]
compare = [[[0 for _ in range(M)] for _ in range(N)] for _ in range(H)]
for height in range(H):
    for row in range(N):
        for col in range(M):
            if graph[height][row][col] == 1 or graph[height][row][col] == 0:
                compare[height][row][col] = 1
            else:
                compare[height][row][col] = -1
dh = [-1, 1, 0, 0, 0, 0]
dr = [0, 0, -1, 1, 0, 0]
dc = [0, 0, 0, 0, -1, 1]
def BFS():
    queue = deque()
    for height in range(H):
        for row in range(N):
            for col in range(M):
                if graph[height][row][col] == 1:
                    queue.append((height, row, col, 0))
    final_time = 0
    while queue:
        height, row, col, time = queue.popleft()
        for h, r, c in zip(dh, dr, dc):
            nh, nr, nc = height + h, row + r, col + c
            if 0<= nh < H and 0 <= nr < N and 0 <= nc < M and graph[nh][nr][nc] == 0:
                graph[nh][nr][nc] = 1
                queue.append((nh, nr, nc, time+1))
        final_time = time
    return final_time
def main():
    time = BFS()
    for height in range(H):
        for row in range(N):
            for col in range(M):
                if graph[height][row][col] != compare[height][row][col]:
                    print(-1)
                    return
    else:
        print(time)

main()