[백준/Python] 7576. 토마토

📄 문제

백준
난이도 : Gold 5
문제 제목 : 토마토

✏️ 풀이 1

import sys
from collections import deque

input = sys.stdin.readline
m, n = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
dist = [[-1] * m for _ in range(n)]

dy = (-1, 0, 0, 1)
dx = (0, -1, 1, 0)
def bfs(start_points):
    deq = deque(start_points)
    result = 0
    
    for point_y, point_x in start_points:
        dist[point_y][point_x] = 0
    
    while deq:
        y, x = deq.popleft()
        current_dist = dist[y][x]
        result = max(current_dist, result)
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny < 0 or nx < 0 or ny >= n or nx >= m:
                continue
            if dist[ny][nx] != -1 or matrix[ny][nx] == -1:
                continue
            deq.append([ny, nx])
            dist[ny][nx] = current_dist + 1
    
    return result

start_points= []
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1:
            start_points.append([i, j])
result = bfs(start_points)

for i in range(n):
    for j in range(m):
        if dist[i][j] == -1 and matrix[i][j] != -1:
            print(-1)
            sys.exit(0)
print(result)

✅ Check Point 1: 우선 이 문제가 BFS 문제임을 파악해야 한다.
이 문제가 BFS 문제인 이유는 다음과 같다.

1. 토마토가 익어가는 상황 자체가 BFS와 같다.
2. 토마토가 다 익기까지 필요한 최소 일수는 모든 익지 않은 토마토들에 대해 가장 가깝게 위치한 토마토까지의 거리를 통해 구할 수 있다.

✅ Check Point 2: 이 문제는 BFS 중에서도 BFS의 기본적인 응용 문제인 '시작점이 여러 개일 때' 의 문제이다.

각 익은 토마토들에 대해 해당 위치를 시작점으로 하는 BFS를 한 번씩 돌리게 되면, BFS의 시간복잡도가 O(NM) 이고, 익은 토마토의 개수가 최대 NM 개일 수 있으니 총 O(N^2M^2) 가 되어 시간초과될 확률이 높다.

따라서 모든 시작점을 큐에 넣고 BFS를 돌도록 해야 한다.

BFS를 알고 있으면서 위의 체크 포인트를 유의하고 위의 코드를 본다면 이해가 쉽게 될 것이다.

📦 GitHub

해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Silver) '7576. 토마토'
GitHub - [9강] BFS/연습문제 '7576. 토마토'

---

BFS의 대표적인 응용 유형인 '시작점이 여러 개일 때' 유형의 가장 기본적인 문제라 정리를 해보았다.