[백준 7576 실버1] 토마토

www.acmicpc.net/problem/7576

7576번: 토마토

해결방안

• BFS를 이용한 방식 사용

알고리즘

1. 토마토 박스 초기화

2. 전체를 돌며 익은 토마토를 큐에 넣어줌

3. bfs

   1. 큐에서 토마토를 꺼내와 상, 하, 좌, 우 토마토에 익은 날짜 + 1을 삽입해줌

4. 전체를 돌며 가장 날짜가 큰 것을 찾음
   1. 0이 들어있다는 것은 토마토가 익을 수 없다는 것이므로 -1을 출력하고 종료

핵심 팁

• 기본적인 BFS문제
• 핵심 포인트는 익은 토마토에 단순히 방문 처리하는 것이 아니라 날짜를 하나씩 추가하여 토마토 값을 갱신 해야함
• 절대 익지 못하는 토마토가 있는 경우는 BFS 종료 후, 별도로 확인하며 처리 가능

from collections import deque
import sys
input = sys.stdin.readline
c, r = map(int, input().split())
tomato_box = list()
move = [(0, -1), (1, 0), (0, 1), (-1, 0)]
for _ in range(r):
    tomato_box.append(list(map(int, input().split())))
days = 0
reap_queue = deque()
for row in range(r):
    for col in range(c):
        if tomato_box[row][col] == 1:
            reap_queue.append((row, col))
while reap_queue:
    s_r, s_c = reap_queue.popleft()
    for x, y in move:
        mv_x, mv_y = s_r + x, s_c + y
        if 0 <= mv_x < r and 0 <= mv_y < c and tomato_box[mv_x][mv_y] == 0:
            reap_queue.append((mv_x, mv_y))
            tomato_box[mv_x][mv_y] = tomato_box[s_r][s_c] + 1
for row in tomato_box:
	# 절대 익지 않는 경우 확인
    if 0 in row:
        print(-1)
        exit(0)
    for j in row:
        if j > days:
            days = j
print(days - 1)

*퍼가신다면 출처와 댓글 부탁드립니다.

*더 많은 자료는 아래 github에 있습니다

https://github.com/griffinGC/Algoritm_PS

https://github.com/griffinGC/TIL_Public