백준 7569 문제 풀이 python

12655 단어 문제풀이BFSBFS

🐒 토마토

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

7576문제의 파생형이다

✍ 나의 풀이

import sys
from collections import deque

input = sys.stdin.readline



M, N, H = map(int, input().split())


matrix = []

for i in range(H):
    matrix.append([])
    for j in range(N):
        matrix[i].append(list(map(int,input().split())))


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


queue = deque()

allgood = True
for i in range(H):
    for j in range(N):
        for k in range(M):
            if matrix[i][j][k] == 1:
                queue.append((i,j,k))
            elif matrix[i][j][k] == 0:
                allgood = False

if allgood:
    print(0)
    exit(0)
 # 모두 익어있으면 0 출력하고 종료

days = 0
while queue:
    for _ in range(len(queue)):
        a,b,c = queue.popleft()

        for i in range(6):
            nz = dz[i] + a
            nx = dx[i] + b
            ny = dy[i] + c

            if 0<=nz<H and 0<=nx<N and 0<=ny<M:
                if matrix[nz][nx][ny] == 0:
                    matrix[nz][nx][ny] = 1
                    queue.append((nz,nx,ny))
    days += 1

for i in range(H):
    for j in range(N):
        for k in range(M):
            if matrix[i][j][k] == 0:
                print(-1)
                exit(0)
                 #탐색이 끝났는데도 익지않은 토마토가 남아있으면 -1출력하고 종료

print(days-1)
 #토마토가 다 익었으면 익는데 걸리는 날을 출력


🧠 문제 이해

3차원 배열과
bfs 알고리즘 구현을 이해하는게 중요할듯.

if 처음부터 모든 토마토가 익어있으면 0을 출력
elif 모든 토마토를 익힐수 없으면 -1을 출력
else 모든토마토를 익히는데 드는 일수를 출력

이전 문제에서 bfs알고리즘에서 한턴씩 탐색하는 법을 배울 수 있었다.

좋은 웹페이지 즐겨찾기