백준[ 7576 | Python ] 토마토

문제

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

풀이

유념해두어야할 조건은 아래 세가지이다.

1. 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력  
   
2. 토마토가 모두 익지는 못하는 상황이면 -1을 출력  
   
3. 위 두 조건이 아닌 경우 토마토가 모두 익을 때까지의 최소 날짜를 출력

익지 않은 토마토는 익은 토마토의 4방향으로부터만 영향을 받기 때문에 그에 해당하는 dx와 dy를 지정해준다.

이 후 주어지는 배열로부터 토마토의 위치를 먼저 구해 deque에 넣어 탐색을 준비한다.
이 때 조건1을 생각해서 익지않은 토마토 0이 한 번이라도 등장할 경우에는 미리 만들어준 switch 변수를 True값으로 바꿔준다.

익은 토마토의 위치로 채워준 deque를 BFS로 탐색해주는데, 이 때 이미 익은 토마토가 하루에 영향을 줄 수 있는 토마토들을 따로 표시해두기 위해 이전 토마토가 익은 날짜에 1을 더해 해당 날짜에 익을 토마토들을 표시해둔다.

익은 토마토들의 최소 날짜를 출력하기 전에 조건 1을 고려해주고, 이미 모두 익은 토마토가 아니었다면
최소 날짜를 구해준다.
마지막으로 첫 토마토가 익은날짜를 1로 시작했기때문에, 출력값에서 1을 빼준뒤 출력해준다.

from collections import deque
import sys
input = sys.stdin.readline
m,n = list(map(int,input().split()))
dx, dy = [-1,1,0,0],[0,0,-1,1]
board = []
q = deque()
switch = False
for i in range(n):
    tomato = list(map(int,input().split()))
    for j in range(len(tomato)):
        if tomato[j] == 1:
            q.append((i,j))
        elif tomato[j] == 0:
            switch = True
    board.append(tomato)

while q:
    nx,ny = q.popleft()
    for i in range(4):
        qx, qy = nx+dx[i],ny+dy[i]
        if 0<=qx<n and 0<=qy<m and board[qx][qy] == 0:
            board[qx][qy] = board[nx][ny]+1
            q.append((qx,qy))

day = 0

if switch:
    for i in board:
        if 0 in i:
            print(-1)
            exit()
        else:
            day = max(day, max(i))
    print(day-1)
    # print(f"day = {day-1}")
else:
    print(0)

생각 & 정리

BFS의 구현까지는 어렵지 않았는데 오히려 조건1을 생각하는 과정에서 고민이 많았다.
모 유튜브에서 접했던대로 switch와 같은 변수를 사용하는 것이 좋지 않다는 것은 알고있었지만 아직 경험이 부족한 것 같다.
앞으로 이와 비슷한 문제를 또 접한다면 미리 걸러낼 조건을 고민해봐야할 것 같다.