[백준/Baekjoon 7569] 토마토 파이썬(Python) 풀이

문제

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

7569번: 토마토

문제핵심

기본적으로 BFS문제이며 핵심은 3차원 리스트를 사용해야한다는 것이 핵심이다.

-> 위 문제를 풀기전에 https://www.acmicpc.net/problem/7576 이것부터 푸는 것을 추천한다.

7576번: 토마토

7576번 해설은

https://youknow301.tistory.com/60

[Baekjoon 7576] 토마토(Python)풀이

 

 

풀이과정

1. M,N,H과 3차원 토마토를 넣을 tomato =  [] 를 선언한다.

2. 좌표를 이용한 bfs이므로 dx, dy,dz 를 입력받는다.

3. 반복문을 통해 tomato 리스트 입력을 받는다.

4. queue를 선언하고 반복문을 통해 tomato[i][j][k]==1일 대 queue에 [i,j,k]를 넣는다.

5. bfs를 진행시킨다.

6. 토마토가 익었는지 확인할 변수 fresh를 선언후 반복문을 통해 토마토가 다 익었는지 확인한다.

7. 다 익었으면 최대값을 익지 않았으면 -1을 출력한다.

 

정답코드

from collections import deque


def bfs():
    while queue:
        z, y, x = queue.popleft()

        for i in range(6):
            X = x + dx[i]
            Y = y + dy[i]
            Z = z + dz[i]
            if 0 <= Z < H and 0 <= X < M and 0 <= Y < N and tomato[Z][Y][X] == 0:
                queue.append((Z, Y, X))
                tomato[Z][Y][X] = tomato[z][y][x] + 1


M, N, H = map(int, input().split())  # N = y, M = x H = z
tomato = [[list(map(int, input().split())) for _ in range(N)] for __ in range(H)]
dx = [0, 0, 1, -1, 0, 0]
dy = [1, -1, 0, 0, 0, 0]
dz = [0, 0, 0, 0, 1, -1]

queue = deque()
for i in range(H):
    for j in range(N):
        for k in range(M):
            if tomato[i][j][k] == 1:  # 토마토가 익어있으면 queue에 집어 넣기
                queue.append([i, j, k])

bfs()
fresh = False
for a in range(H):
    for b in range(N):
        for c in range(M):
            if tomato[a][b][c] == 0:
                fresh = True
                break


if fresh:
    print(-1)
else:
    print(max(max(map(max, row)) for row in tomato)-1)

 

문제평 및 새롭게 알게된 것

만약 백준 7576을 무난히 풀었다면 어렵게 풀지않았을 것이라고 생각한다. 그렇지만 3차원 리스트를 생각해야해서 7576번 보다는 확실히 더 어려운 감이 있었다. 의외로 마지막 3차원 리스트에서 가장 큰 수를 구하는 법이 복병이였다.

 

3차원 리스트에서 가장 큰 수를 찾기위해서는 max(max(map(max,row)) for row in tomato))를 이용해야 한다는 것을 알았다.