[BaekJoon] 백준 7569번 토마토 - Python

[BaekJoon] 백준 7569번 토마토 - Python

 

🎈문제

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

7569번: 토마토

💬설명

• 처음에 bfs로 큐를 써서 풀려고 하다가 적용하지 않고 풀어봤다.
• 대신 시간 초과에 걸려서 pypy로 채점했다.
• 확실하게 시간 단축해서 풀고 싶으면 queue로 풀어줘야 할듯
• 풀이는 간단하다. 매일 추가된 익은 토마토에 대해 6개 방향을 체크해서 익은 토마토의 개수와 전체 토마토의 개수가 같다면 출력 후 종료. 만약 하루가 지났는데 지나기전에 체크한 익은 토마토 개수와 지난 후에 체크한 익은 토마토 개수가 같다면 더이상 변화가 없을 것이므로 -1출력 후 종료.

 

👩‍💻코드

import sys
input = sys.stdin.readline


M, N, H = map(int, input().split())
tomato_sum = 0  # 토마토 개수
tomato_cmpl = 0  # 익은 토마토 개수
tomato = []  # 익은 토마토 위치
arr = [[[0 for _ in range(M)] for _ in range(N)] for _ in range(H)]
for i in range(H):
    for j in range(N):
        arr[i][j] = list(map(int, input().split()))
        for k in range(M):
            if arr[i][j][k] == 1:
                tomato.append([i, j, k])
                tomato_cmpl += 1
                tomato_sum += 1
            elif arr[i][j][k] == 0:
                tomato_sum += 1

#  6개의 방향
dh = [1, 0, 0, -1, 0, 0]
dn = [0, 0, 1, 0, 0, -1]
dm = [0, 1, 0, 0, -1, 0]

# 만약 이미 다 익어있다면
if tomato_cmpl == tomato_sum:
    print(0)
    exit()

day = 0
new_tomato = []
while True:
    day += 1
    before_tomato = tomato_cmpl

    for t in tomato:
        for i in range(6):
            nh = t[0] + dh[i]
            nn = t[1] + dn[i]
            nm = t[2] + dm[i]

            if nh < 0 or nn < 0 or nm < 0 or nh >= H or nn >= N or nm >= M:
                continue

            if arr[nh][nn][nm] != 0:
                continue

            tomato_cmpl += 1
            arr[nh][nn][nm] = 1
            new_tomato.append([nh, nn, nm])
            if tomato_cmpl == tomato_sum:
                print(day)
                exit()

    tomato = new_tomato[:]
    new_tomato = []

    if before_tomato == tomato_cmpl:
        print(-1)
        exit()