[백준] 7569번: 토마토(그래프이론, Python)

문제 링크

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

7569번: 토마토

 

문제 풀이

풀이 설명

• 분류: 그래프이론
• 1 익은 것, 0 안익은것, -1 없음
• 1 부터 BFS 전파 (1의 위치를 담은 큐)
• 큐가 끝날때까지 반복, 큐가 끝났을 때, 0이 1개라도 있으면 -1  (원래 토마토 자리를 알아놓자)
• 안익은 토마토가 익는 0 -> 1로 변하는 것이 모든 0의 수와 같은 count면 전부 익었다고 할 수 있다.

코드

# - 익은 토마토의 자리 위치, 토마토 위치(-1 출력을 위해) 자리 받아놓기
# - 익은 토마토부터 BFS 시작 전염된 것은 큐에 넣기
# - day를 포함해서 큐에 넣기
# - day가 빠른 것부터 꺼내쓰는 우선순위큐
# - 마지막 day 출력

import sys
from collections import deque

input = sys.stdin.readline

M, N, H = map(int, input().split())
box = [[] for _ in range(H)]
q = deque([])
cnt = 0 # 1을 count 하는 숫자 -> ans -= cnt
day = 0
ans = M * N * H

# input
for i in range(H):
    for j in range(N):
        line = list(map(int, input().split()))
        box[i].append(line)
        done = list(filter(lambda x: line[x] == 1, range(M)))
        ans -= len(list(filter(lambda x: line[x] == -1, range(M))))
        for k in done:
            q.append((i, j, k))
        cnt += len(done)

if ans - cnt == 0:
    print(0)
else:
    dx = [-1, 1, 0, 0, 0, 0]
    dy = [0, 0, -1, 1, 0, 0]
    dz = [0, 0, 0, 0, -1, 1]

    while q:
        z, x, y = q.popleft()

        for i in range(6):
            nz, nx, ny = z + dz[i], x + dx[i], y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= M or nz < 0 or nz >= H:
                continue
            if box[nz][nx][ny] == -1:
                continue

            # 해당 위치
            if box[nz][nx][ny] == 0:
                box[nz][nx][ny] = box[z][x][y] + 1
                day = max(day, box[nz][nx][ny])
                q.append((nz, nx, ny))
                cnt += 1


    if ans == cnt:
        day -= 1
    else:
        day = -1

    print(day)