[Baekjoon]백준 7576 토마토(골드 5) - Python

문제설명

예제

문제를 살펴보면 익은 토마토 옆으로 토마토가 익어가게 되는데, 대각선이 아닌 바로 옆, 위, 아래만 해당된다

따라서 이전 문제에서 주로 사용하였던 dx = [-1, 1, 0, 0], dy = [0, 0, -1, 1]을 사용하면 된다

해당 문제에서는 이전에 queue()를 선언할 때, deque([(x, y)])과 같은 방식으로 선언해주었지만, 

1인 토마토(익은 토마토)에서 출발해야하기 때문에 append()하는 과정이 추후에 이루어져야한다

그래서 이번에는 bfs() 함수에 전달하는 인자 없이 그냥 작성해주면 된다(python)

2중 for문을 통해 모든 창고를 확인하며 익은 토마토의 위치를 확인하고 해당 위치를 queue에 추가해준다

이후 이전과 동일하게 while queue: 과정을 통해 탐색을 해나가면된다

 

마지막에 총 며칠이 걸렸는지 확인하는 과정이 필요한데, 만약 모든 토마토가 익지 못하였다면 -1을 출력해야하기 때문에

이번에도 2중 for문을 통해 모든 창고의 값(토마토)을 확인하여 0이 존재한다면 이는 

주변 환경에 의해 익지 못하였다는 말이기 때문에 print(-1)을 하고 exit()을 통해 코드가 종료되어야한다

만약 그것이 아니라면 day의 최대값을 찾아서 이를 저장해주면된다

여기서 마지막으로 주의할 점은 bfs()과정에서 익은 토마토의 위치에 +1을 하며 탐색했기때문에

시작하는 값인 1(익은 토마토의 값)에 +1을 하게된것이다 따라서 마지막에 day-1하는 과정이 필요하다

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs():
    queue = deque()
    for i in range(length):
        for j in range(width):
            if storage[i][j] == 1:
                queue.append([i, j])
                
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < length and 0 <= ny < width and storage[nx][ny] == 0:
                storage[nx][ny] = storage[x][y] + 1
                queue.append((nx, ny))
        
                
width, length = map(int, input().split())
storage = [list(map(int, input().split())) for _ in range(length)]

bfs()

day = 0
for i in range(length):
    for j in range(width):
        if storage[i][j] == 0: # 토마토를 다 익히지 못한 경우
            print(-1)
            exit()
    day = max(day, max(storage[i]))
    
print(day-1)