[백준] 7569 토마토

🔗 문제 링크

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

💻 코드

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

# 최소일수: BFS
dq = deque()
m,n,h = map(int,input().split())
tomato = []
visited = [[[0 for _ in range(m)] for _ in range(n)] for _ in range(h)]

for i in range(h):
    tomato.append([])
    for _ in range(n):
        tomato[i].append(list(map(int,input().split())))
        
def contains_zero(arr):
    for sub_arr in arr:
        for inner_arr in sub_arr:
            if 0 in inner_arr:
                return 1
    return 0

def is_valid(z,x,y):
    if 0 <= z < h:
        if 0 <= x < n:
            if 0 <= y < m:
                return 1
    return 0
        
    
def bfs():

    dir = [
        [-1,0,0], [1,0,0],
        [0,1,0], [0,0,-1], [0,-1,0], [0,0,1]
    ]

    
    while dq:
        ch, cx,cy,day = dq.popleft()

        for i,j,k in dir:
            nh = ch+i
            nx,ny = cx+j, cy+k 
            if is_valid(nh,nx,ny):
                if not visited[nh][nx][ny]:
                    if tomato[nh][nx][ny] == 0:
                        tomato[nh][nx][ny] = 1
                        visited[nh][nx][ny] = 1
                        dq.append((nh,nx,ny,day+1)) 

    return day
        
if not contains_zero(tomato):
    print(0)
    exit(0)

for i in range(h):
    for j in range(n):
        for k in range(m):
            if tomato[i][j][k] == 1:
                dq.append((i,j,k,0))
                visited[i][j][k] = 0

if not dq:
    print(-1)
    exit(0)
    
result = bfs()
if contains_zero(tomato):
    print(-1)
else:
    print(result)
    

🤷‍♂ 풀이

• 처음에 계속 틀렸는데 이유가 맨처음 좌표가 1이되는 시작점부터 시작했기 때문이다.

  • 동시에 시작해야하므로, 다중 시작점 BFS로 접근해야한다.

• UnboundLocalError: bfs함수를 실행할 때, tomato가 1이아닌 곳만 있어서 deque가 비어있을 수 있다. 이런 경우에는 토마토가 익을 수 없기에 -1을 출력해줘야한다.

• 다중시작점을 제외하고는 일반 BFS와 동일하게 풀면되는데, 토마토상자가 높이까지 존재하다보니까 3차원 배열을 사용해서 푸는 것이 적절하다.