BFS : 토마토(백준 7569번)

▶ 문제 : https://www.acmicpc.net/problem/7569

7569번: 토마토

##### 문제 #####
# 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 
# 토마토는 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.
# 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 
# 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면,
# 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 
# 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 
# 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 
# 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.
# 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 
# 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 
# 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 
# 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

##### 입력 #####
# 첫 줄에는 상자의 크기를 나타내는 두 정수 M, N과
# 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. 
# M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 
# 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 
# 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 
# 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 
# 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 
# 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 
# 이러한 N개의 줄이 H번 반복하여 주어진다.
# 토마토가 하나 이상 있는 경우만 입력으로 주어진다.

##### 출력 #####
# 여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 
# 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 
# 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

▶ 접근 방법

가로, 세로, 높이의 3차원 정보를 어떻게 구현할 것인지가 관건이었다.
아래 풀이에서는 똑같은 가로(row), 세로(column) 정보의 토마토를
높이(height)만큼 갖고 있는 리스트를 구현하여 문제를 해결하였다.

 

▶ 풀이 코드

import sys
from collections import deque

# 익은 토마토를 기준으로 BFS를 진행한다.
def BFS(result):
    while queue:
        h, r, c = queue.popleft()
        # 3차원 방면으로 모두 탐색해준다.
        for dh, dr, dc in (-1, 0, 0), (1, 0, 0), (0, -1, 0), (0, 1, 0), (0, 0, -1), (0, 0, 1):
            nh, nr, nc = h + dh, r + dr, c + dc

            # 탐색 중 익지 않은 토마토가 있다면 변화 시켜준다.
            if 0 <= nh < h and 0 <= nr < r and 0<= nc < c and tomatos[nh][nr][nc] == 0:
                tomatos[nh][nr][nc] = tomatos[h][r][c] + 1
                result = max(tomatos[nh][nr][nc], result)
                queue.append([nh, nr, nc])

# 가로, 세로, 높이 정보를 입력받는다.
column, row, height = map(int, sys.stdin.readline().split())

# 토마토 정보를 입력 받아 tomatos라는 변수에 담는다.
tomatos = []
for _ in range(height):
    temp = []
    for _ in range(row):
        temp.append(list(map(int, sys.stdin.readline().split())))
    tomatos.append(temp)

queue = deque()
already_done = True
# tomatos를 모두 확인하면서 토마토가 익은 경우라면 해당 위치를 queue에 넣어준다.
# 만약 익지 않은 경우가 있다면, already_done이라는 변수를 False로 바꾸어준다.
for h in range(height):
    for r in range(row):
        for c in range(column):
            if tomatos[h][r][c] == 1:
                queue.append([h, r, c])
            if tomatos[h][r][c] == 0:
                already_done = False

result = -1
BFS(result)

# tomatos를 탐색하는 중에 익지 않은 경우가 하나라도 발생하면 -1을 출력하고 프로그램을 멈춘다.
for h in range(height):
    for r in range(row):
        for c in range(column):
            if tomatos[h][r][c] == 0:
                print(-1)
                sys.exit(0)
                
# 모두 다익었다면 0을 출력한다.
if already_done:
    print(0)
else :
    print(result-1)

 

▶ 관련 링크

2021.11.18 - [알고리즘] - BFS(Breadth First Search, 너비 우선 검색)이란?

2021.11.19 - [알고리즘] - BFS : 미로 탐색(백준 2178번)

2021.11.19 - [알고리즘] - BFS : 특정 거리의 도시 찾기(백준 18352번)

2021.11.19 - [알고리즘] - 다익스트라 알고리즘(Dijkstra Algorithm)이란?

2021.11.19 - [알고리즘] - BFS : 최소비용 구하기(백준 1916번)

2021.11.20 - [알고리즘] - BFS : 미로만들기(백준 2665번)

2021.11.20 - [알고리즘] - BFS : 탈출(백준 3055번)

2021.11.20 - [알고리즘] - BFS : 동전 2(백준 2294번)