(백준-7569) 토마토 - 파이썬

문제 (백준 - 7569 토마토)

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

---

문제 이해

• 토마토 상자가 위 아래로 쌓여있다.
• 토마토 상자 안에 있는 토마토는 익은 토마토, 익지 않은 토마토, 토마토가 없는 칸이 있다.
• 익은 토마토는 자신의 위치를 기준으로 앞, 뒤, 왼쪽, 오른쪽, 위, 아래의 익지 않은 토마토를 하루 뒤면 익게 만든다.

구할 것

• 익은 토마토에 의해 토마토 상자 안에 있는 모든 토마토들이 익을때 까지의 최소 일수를 출력하는 것입니다.
• 주의할점은!! 만약 토마토가 모두 익지 못하는 상황이면 -1을 출력해야 합니다!

---

문제 접근

문제에 나와있는 입력의 테케들과 익은 토마토와 인접한 토마토들이 익는다를 보니 그래프 탐색인 것이 바로 보입니다.

그렇다면 그래프 탐색의 DFS와 BFS중 어떤 것을 사용해야 할까요?

바로, BFS(너비우선탐색)입니다. 익은 토마토들과 인접한 익지않은 토마토들을 방문해야 하기 때문입니다.

• 이 문제를 풀 때 구현하는데 있어 있었던 문제는 2가지 입니다.

1. 상자가 위 아래로 높이가 존재하기 때문에 3차배열을 사용해야 합니다.

2. 입력 조건에 1은 익은 토마토 0은 익지않은 토마토, -1은 비어있는 칸이라고 주어졌는데

   익은 토마토(1)과 인접한 익지않은 토마토(0)을 방문하기 위해서는 한 칸에서만 BFS를 하게되면

   정답을 도출할 수 없게 됩니다.

이에 대한 해결방안

1. 3차원 배열은 사용해보지 않았기 때문에 낯설었습니다. 그냥 구현해보았습니다.

2. 2번째 문제는 BFS를 실행하기 전 큐(Queue)에 미리 익은 토마토들을 넣어놓았습니다.

   큐 특성상 먼저 들어간 데이터에 대하여 먼저 처리하기 때문에 익은 토마토와 인접한 토마토

   들을 전반적으로 탐색할 수 있게 됩니다!

자세한 것은 코드를 보시면 될 것 같습니다!

---

코드

import sys
from collections import deque
input = sys.stdin.readline

# 토마토가 다 익을때 까지의 최소 일수를 계산하여 출력
# m: 가로, n: 세로, h: 높이
m, n, h = map(int, input().strip().split())

# 1: 익은 토마토, 0: 익지 않은 토마토, -1: 토마토가 들어있지 않은 칸
box = []

# 상자의 정보 입력받기
for _ in range(h):
    temp = []
    for _ in range(n):
        temp.append(list(map(int, input().strip().split())))
    box.append(temp)

# 오, 왼, 앞, 뒤, 위, 아래
move = [[0, 0, 1], [0, 0, -1], [0, 1, 0], [0, -1, 0], [1, 0, 0], [-1, 0, 0]]

# 큐 생성
queue = deque()

# bfs정의
def bfs():
    while queue:
        nh, nrow, ncol = queue.popleft()
        for i in move:
            mh = nh + i[0]
            mrow = nrow + i[1]
            mcol = ncol + i[2]
            if mrow >= 0 and mcol >= 0 and mh >= 0 and mrow < n and mcol < m and mh < h:
                if box[mh][mrow][mcol] == 0:
                    box[mh][mrow][mcol] = box[nh][nrow][ncol] + 1
                    queue.append((mh, mrow, mcol))
                    
# 초기 입력값에서 익은 토마토(1)의 위치 정보를 큐에 미리 넣어놓는다.             
for hei in range(h):
    for row in range(n):
        for col in range(m):
            if box[hei][row][col] == 1:
                queue.append((hei, row, col))

# 너비우선탐색 실행
bfs()

# 최댓값을 찾는다.
max_value = 0
for h in range(h):
    for r in range(n):
    	# 만약 0이 존재한다면 토마토가 다 익을 수 없는 상황이므로 -1을 출력하고 종료한다.
        if 0 in box[h][r]:
            print(-1)
            exit()
        if max_value < max(box[h][r]):
            max_value = max(box[h][r])


print(max_value - 1)

후기

3차원 배열을 처음 사용해보는 문제였습니다. 그렇다보니 문제를 푸는데 있어 살짝 복잡함은 있었지만 BFS의 원리를 이용하니 정말 쉽게 풀 수 있었던 문제였습니다!