[백준] 토마토

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

7569번: 토마토

bfs를 활용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

상자안에 익은 토마토, 안익은 토마토, 빈칸이 존재합니다. 이 때, 매일 익은 토마토 옆에 있는 안익은 토마토가 익을 때, 모든 토마토가 익기 위한 일 수를 구해야 합니다.

 

<Solution>

bfs를 이용하면 되는 간단한 문제입니다. bfs의 초기 queue에 1인 지점들의 좌표를 넣어줍니다. (익은 토마토의 좌표를 넣습니다.)

ex ) deque([[0, 1, 2, 0]]) -> 높이, row, column, tmp(일수 check용)

5 3 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0

그리고 bfs를 순환하며 만약 안익은 토마토가 존재할 시 tmp값을 1씩 증가시키면서 visited로 관리를 하는 형태로 문제를 해결하면 됩니다. 

 

실제 구현은 아래와 같습니다.

import sys
from collections import deque

d_row = [0, 0, -1, 1]#left right up down
d_column = [-1, 1, 0, 0]
d_height = [-1, 1]

m, n, h = list(map(int, sys.stdin.readline().rstrip().split()))#가로 세로 높이

tomatos = [[list(map(int, sys.stdin.readline().rstrip().split()))for _ in range(n)] for _ in range(h)]
tomatos.reverse()

visited = [[[-1 for _ in range(m)] for _ in range(n)] for _ in range(h)] # not visited = -1 / visited = 1

q = deque()
for k in range(h):
    for i in range(n): # row
        for j in range(m): # column
            if tomatos[k][i][j] == 1:
                q.append([k,i,j,0])
                visited[k][i][j] = 1
                
tmp = 0         
while(q):
    # print(q)
    k_, i_, j_, tmp = q.popleft()
    for t in range(4):
        new_i = i_ + d_row[t]
        new_j = j_ + d_column[t]
        if 0<=new_i<n and 0<=new_j<m:
            if visited[k_][new_i][new_j] == 1 or tomatos[k_][new_i][new_j] == -1:
                continue
            tomatos[k_][new_i][new_j] = 1
            visited[k_][new_i][new_j] = 1
            q.append([k_,new_i,new_j,tmp+1])

    for t_ in range(2):
        new_k = k_ + d_height[t_]
        if 0<=new_k<h:
            if visited[new_k][i_][j_] == 1 or tomatos[new_k][i_][j_] == -1:
                continue
            tomatos[new_k][i_][j_] = 1
            visited[new_k][i_][j_] = 1
            q.append([new_k, i_, j_, tmp+1])
# print(f'tomatos : {tomatos}')
          
for k in range(h):
    for i in range(n): # row
        for j in range(m): # column
            if tomatos[k][i][j] != 0:
                continue
            else:
                tmp = -1
                break

print(tmp)