[백준 7576] 토마토 (python)

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

7576번: 토마토

 

토마토 문제

상자안에 놓여있는 토마토가 옆으로 갈수록 익어가는데, 전체 토마토가 익는데 걸리는 최소 일 수를 찾는 문제

BFS를 활용하여 풀면 간단하게 해결 할 수 있는 문제

내가 푼 정답코드

def ripe():
    while queue:
        y, x = queue.popleft()
        for dy, dx in spread:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < M and tomato[ny][nx] == 0:
                tomato[ny][nx] = tomato[y][x] + 1
                queue.append([ny, nx])

import sys
from collections import deque
M, N = map(int, sys.stdin.readline().split())
tomato = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
spread = [[1,0],[-1,0],[0,1],[0,-1]] # 이동 값
queue = deque()
out = 0

for i in range(N):
    for j in range(M):
        if tomato[i][j] == 1:
            queue.append([i,j])

ripe() # 탐색을 돌리자

for i in tomato: 
    for j in i: #전체 토마토에 대해
        if j == 0: # 돌렸는데 0이 남아있으면
            out = 1 # 1 저장

if out == 0: # 전부 익었다면
    print(max(map(max,tomato))-1) # 토마토 내에서 제일 큰값 -1
elif out == 1: # 안익는 부분 있다면
    print(-1) # -1 출력

미로 탐색할때 걸리는 최소 거리를 구하는 문제와 동일한 형태의 문제이다.

다만 중간에 토마토가 1개가 아니라 여러 개로부터 퍼지는 경우도 고려를 해줘야하는데, 이건 그냥 처음에 queue에 넣고 시작하면 queue에 선입선출 구조에 의해 자연스레 여러 개로부터 퍼지는 경우수도 고려해준다.

미로 거리 찾기 문제를 풀어봤고, queue의 구조를 잘 이해하고 있다면 쉽게 풀 수 있는 문제

---

느낀 점

처음에 토마토 1개에서 시작하는줄 알았는데, 토마토 여러 개에서 시작하는 케이스도 있어서 이점까지 고려를 해줘야한다는 부분에서 어떻게 해결해야하지? 하고 한참을 고민했다. 생각해보니 큐의 선입선출 구조를 생각하면 그냥 시작 지점만큼 넣어주면 된다는 간단한걸 떠올려서 해결했다.

BFS 연습을 하기에 좋았던 문제였다고 생각한다!