[백준 파이썬] 7576 토마토

📌문제 출처

솔브닷 클래스 3+ 단계
https://www.acmicpc.net/problem/7576

7576번: 토마토

❓ 문제

 

❗ 풀이

• BFS 응용

📗 풀이 코드

import sys
from collections import deque
input = sys.stdin.readline
# bfs 생성
def bfs(): # 익은 토마토 위치(y행, x열)로부터 다음날 익게되는 토마토 위치 추가
    global stack, not_good
    cnt = 0 # 최초 날짜
    while stack:
        y,x,cur = stack.popleft()
        if cur!=cnt : # 날이 넘어갔으면 토마토 확인
            if not not_good : # 모든 토마토가 익었다면
                return cur # 다 익은 날 출력
            else : # 다 익지 않았다면
                cnt += 1 # 날짜 하루 경과
        cur += 1 # 다음번 bfs로 넣을 때는 다음 날짜로 진행
        for i in range(4):
            ny,nx = y+dy[i],x+dx[i]
            if 0<=ny<n and 0<=nx<m and tomato[ny][nx]==0 : # 이동가능하고 안익은 토마토라면
                tomato[ny][nx] = 1 # 익은 토마토 추가
                not_good -= 1
                stack.append([ny,nx,cur]) # 익은 토마토 bfs 추가
    return -1 # 안 익은 토마토가 있지만 stack이 끝난다면 다 익는게 불가능이므로 -1 출력
m,n = map(int,input().split())
tomato = []
stack = deque()
not_good = 0 # 전체 개수, 안 익은 개수
dy,dx = [-1,1,0,0],[0,0,-1,1]
for i in range(n):
    row = list(map(int,input().split()))
    for j in range(m):
        if row[j]==1: # i행 j열에 익은 토마토가 있다면
            stack.append([i,j,0]) # stack에 토마토 위치, 현재날짜(0) 추가
        elif row[j]==0: # 안 익은 토마토가 있다면
            not_good += 1 # 안 익은 토마토 개수 추가
    tomato.append(row)
if not not_good: # 안 익은 토마토가 없다면
    print(0)
else : # 안 익은 토마토가 있다면
    print(bfs()) # bfs 진행

📗 코드 해설

• bfs 출발 위치가 여러개일 수 있으므로 입력값을 받을 때부터 확인해준다.
  익은 토마토가 있는 위치는 stack에 넣어주고, 안 익은 토마토의 개수를 하나씩 세준다.
• 경우의 수를 줄이기 위해 만약 애초에 안 익은 토마토가 없다면 0을 출력하고 bfs를 진행한다.
• 안 익은 토마토가 있다면 맨 처음 stack에 넣어준 값들부터 bfs를 시작한다.
• bfs에서는 익은 토마토 위치에서 사방의 토마토를 확인하고 안 익은 토마토가 있다면 그 토마토를 익히고(1로 만들고)
  stack에 해당 토마토의 위치와 그 토마토가 익은 날짜를 추가한다.
• 하루의 날짜가 지날 때마다 안 익은 토마토의 개수를 세서 모두가 익었다면 해당 일자를 반환한다.
• bfs에서 현재 날짜(cnt)와 확인하려는 토마토의 날짜(cur)가 다르다면 하루가 지난 것이므로 그때 안 익은 토마토의 개수를 확인한다.
  만약 안 익은 토마토가 남아있다면 현재 날짜를 하루 추가해주고 bfs를 진행한다.
• 그리고 다시 이번 날짜(cur)에 익은 토마토의 사방을 살피고 안 익은 토마토가 있다면 그 토마토를 익히고 stack에 다음 날짜(cur+1)을 넣어준다.