[백준] 7576번 토마토 - 파이썬

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

7576번: 토마토

풀이

전제 조건.

1, "익은" 토마토가 존재한다면 창고에서 1로 표현된다.

2, "익지않은" 토마토가 존재한다면 창고에서 0으로 표현된다.

3, 창고 안에는 벽이 존재하는데 이 벽은 인접한 토마토가 익지않게 막는다. 창고에서 -1로 표현된다.

 

목표: 창고안에 존재하는 토마토가 전부 익을 수 있다면 익게되는데 걸리는 최소 일 수를 출력한다. 만일 창고 안의 모든 토마토가 익지 못한다면 -1을 출력한다.

 

위에 주어진 전제 조건을 완벽히 이해했다면 BFS를 사용해야한다는 것을 알게 될 것입니다.

이를 위해서 deque를 이용하여 BFS코드를 구현해줍니다.

 

구현 순서

1, 이중리스트 안에서 일 수를 저장하도록 구현한다.

2, 익은 토마토의 위치를 확인하여 deque에 넣어준다.

3, BFS함수를 실행하여 이중리스트 안에서 익게 되는 토마토의 위치를 <이전 토마토가 익는데 걸린 일 수 + 1> 로 바꾸어 저장해준다.

4, BFS함수의 실행을 마친 뒤에 이중 for문을 통해서 창고 안에 토마토가 전부 익었는지 확인하며 전부 익었다면 소요된 최소 일 수를 출력한다.

 

# 7567번 토마토
from collections import deque
import sys

# 입력값으로 가로 세로를 받아준다.
M, N = map(int, input().split())

# 창고를 구현해줄 이중리스트 grid를 구현해준다.
grid = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# 최소 일 수를 표현할 정수 변수
days_ans = 0

# 덱 구현
queue = deque()

# 익은 토마토가 효력을 발휘할 수 있는 범위
dxys = ((0,1),(0,-1),(1,0),(-1,0))

def bfs():
    while queue:
        cur_x, cur_y = queue.popleft()
        for dx, dy in dxys:
            nx, ny = cur_x + dx, cur_y + dy
            if 0 <= nx < M and 0 <= ny < N and grid[ny][nx] == 0:
                grid[ny][nx] =  grid[cur_y][cur_x] + 1
                queue.append([nx, ny])

# 익은 토마토의 위치를 파악하여 deque에 넣어준다.
for y in range(N):
    for x in range(M):
        if grid[y][x] == 1:
            queue.append([x,y])
                
# bfs함수를 실행.           
bfs()

# 창고 안의 토마토가 전부 익었는지 확인하고 만일 전부 익지않았다면 -1 출력
# 전부 익었다면 걸린 최소 일 수를 출력
for i in range(N):
    for j in range(M):
        if grid[i][j] == 0:
            print(-1)
            exit(0)
        days_ans = max(days_ans, grid[i][j])

# 익은 토마토가 창고 안에서 1로 표현된다는 것을 이용하여 일 수를 계산해주었기 때문에 -1을 해준다.
print(days_ans-1)

출력결과