[백준] 7569번 토마토 (Python 파이썬)

www.acmicpc.net/problem/7569

7569번: 토마토

문제 설명

가로 M, 세로 N 의 토마토 상자가 H높이만큼 쌓여져 있다. 즉 3차원 배열의 형태로 쌓여져 있다.

이 토마토는 보관 후 하루가 지나면 익은 토마토들의 인접(상하좌우위아래)한 토마토들이 모두 익게 된다.

이 토마토들이 모두 익게되는데 며칠이 걸리는지 최소 일수를 구하면 된다.

---

풀이 과정

토마토들의 좌표는 graph[x][y][z]로 나타낼 수 있다. 기존 문제들과의 차이점이라고 한다면, 보통 BFS문제는 2차원적인 문제가 많이 나오다 보니 방향을 상하좌우만 신경을 쓰면 되었지만, 이 문제는 3차원 문제이므로 위 아래로 방향을 추가해 주어야 한다.

 

코드에서,

today_queue는 오늘 익게 된 토마토들의 좌표들을 저장하는 큐이다.

next_queue는 내일 익게 될 토마토들의 좌표들을 저장하는 큐이다.

 

먼저 find_start()를 통해 제일 처음에 익은 토마토들의 위치를 찾아낸 후에, next_queue의 첫 좌표로 저장한다.

0일(카운트 시작 전날)에 이미 익은 토마토들을 저장하는 것이다.

그리고 그 지점들로부터 BFS를 수행하며 count를 하나씩 높여준다. (count는 일 수)

방식은 전날의 next_queue를 today_queue로 복사하여 오늘의 할당량을 준비한다.

그리고 오늘의 할당량에서 하나씩 꺼내며 탐색을 한다. ( 이 때, next_queue에서도 꺼내주어야 한다. 그렇지 않으면 다음날도 똑같은 자리에서 재탐색 하므로)

탐색을 하며 주변에 아직 익지않은 토마토들의 상태를 익은 상태로 변경해주고 그 토마토들의 좌표들을 next_queue에 저장해주는 방식이다.

from collections import deque
import copy

m, n, h = map(int, input().split())
graph = [[] for _ in range(h)]

dx = [0,0,0,0,1,-1]
dy = [0,0,1,-1,0,0]
dz = [1,-1,0,0,0,0]

next_queue = deque()
count = 0
flag = 0

for i in range(h):
    for j in range(n):
        graph[i].append(list(map(int, input().split())))

def find_start():
    for i in range(h):
        for j in range(n):
            for k in range(m):
                if graph[i][j][k] == 1:
                    next_queue.append((i, j, k))

def bfs():
    global count
    today_queue = copy.deepcopy(next_queue)

    while today_queue:
        x, y, z = today_queue.popleft()
        next_queue.popleft()
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
            if nx < 0 or nx >= h or ny < 0 or ny >= n or nz < 0 or nz >= m:
                continue
            if graph[nx][ny][nz] == 0:
                graph[nx][ny][nz] = 1
                next_queue.append((nx, ny, nz))
    count += 1


find_start()
while next_queue:
    bfs()

for i in range(h):
    for j in range(n):
        if 0 in graph[i][j]:
            flag = 1

if flag == 1:
    print(-1)
else:
    print(count-1)

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !