[탐색/BFS] 백준 7576 토마토 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

7576번: 토마토

 

 

 

2. 문제 풀이

 모든 토마토가 다 익는 데 걸리는 시간을 구하는 문제입니다. 익은 토마토의 상하좌우에 안 익은 토마토가 있으면, 하루 뒤에 익게 됩니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 BFS문제입니다. 주변 토마토부터 탐색합니다. 다만, 기존 BFS처럼 한 곳부터 계속 주변을 탐색하면 안됩니다. 익은 토마토를 우선 조사해서, 순서대로 BFS 조사를 해나가야 합니다.

 

 

 

3. 코드

from collections import deque
import sys
input = sys.stdin.readline

#입력
M, N = map(int, input().split()) #가로, 세로
tomato = []
queue = deque()
for i in range(N):
    tomato.append(list(map(int, input().split())))
    for j in range(M):
        # 잘 익은 토마토의 위치를 Queue에 입력
        if tomato[i][j] == 1:
            queue.append((i, j))

 먼저 queue에 잘 익은 토마토를 저장합니다. 그래야 하루가 지날 때마다, 익은 토마토 주위의 안 익은 토마토가 순차적으로 익습니다.

 기존의 BFS처럼 주변에 익은 토마토가 있으면, 그 토마토를 바로 queue에 넣고 탐색하면 한 쪽만 익습니다...

 

 1 0 0           1 1 0          1 1 1        1 1 1
 0 0 0    =>   1 0 0   =>   1 1 0  =>  1 1 1
 0 0 1           0 0 1          1 0 1        1 1 1     (3일 소요)

 위와 같이 한 쪽만 탐색하면 안됩니다.

 

 1 0 0           1 1 0          1 1 1
 0 0 0    =>   1 0 1   =>   1 1 1
 0 0 1           0 1 1          1 1 1    (2일 소요)

 익은 토마토를 모두 queue에 넣고, 번갈아가며 탐색을 해야 합니다.

 

 

#BFS 탐색
day = 0 #토마토가 다 익는 데 걸리는 시간
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]] #상하좌우 이동
while queue:
    x, y = queue.popleft() #큐에서 토마토 위치 꺼냄
    #토마토 주위 상하좌우 탐색
    for dx, dy in direction:
        a, b = x + dx, y + dy
        #a, b가 모두 범위를 안 벗어나면서, 안 익은 토마토를 발견할 때
        if 0 <= a < N and 0 <= b < M and tomato[a][b] == 0:
            queue.append((a, b)) #익을 토마토
            tomato[a][b] = tomato[x][y]+1​

 queue에 익은 토마토를 번갈아 넣어주면서, 날마다 순차적으로 확장합니다.

 tomato에는 확장될 때마다 +1씩 늘리며 익은 날짜를 기록합니다.

 

 

check = False #안 익은 토마토 있는지
for i in tomato:
    for j in i:
        #안 익은 토마토 발견
        if j == 0:
            check = True
            break
    #안 익은 토마토가 있을 시 -1 출력 후 종료
    if check:
        print(-1)
        break
    day = max(day, max(i))
# 다 익었을 경우, 걸린 일수 출력
else:
    print(day-1) #맨 처음 익은 토마토 1은 필요 일수에서 제외

  BFS탐색이 끝난 후 안 익은 토마토가 있는지 판별하고, 없으면 최대 날짜를 출력합니다.