[백준 7576] 토마토 (C++)

이 문제는 근본적으로는 거리를 구하는 문제이다. 즉, 문제에서 주어진 익은 토마토로부터, 가장 멀리 떨어진 익지 않은 토마토까지의 거리를 구하면, 토마토가 익는데 걸리는 최소 날짜가 구해진다.

따라서, 이 문제는 거리를 구하는 문제이므로 BFS로 접근하는 것이 좋아보인다.

이 문제에서는 익은 토마토가 여러 개 주어질 수 있는 상황이므로, 이를 처리하기 위해 입력을 받을 때, 1이라면 큐에 먼저 추가해 놓도록 해서, BFS의 시작점을 곧바로 찾을 수 있도록 하자.

원래라면, 원본 배열인 board를 오염시키는 것이 매우 위험할 수 있다. 하지만, 우리는 PS를 하는 입장이고 원본을 유지하라는 조건이 없기 때문에 board를 곧바로 수정해서 메모리를 아껴보도록 하자.

BFS를 진행하면서, 범위를 벗어나거나 board가 0이 아닌 값이면 건너뛰고, 그렇지 않다면 큐에 해당 위치를 삽입하고 거리를 1증가시켜 해당 위치에 저장시키면 된다.

현재, 우리는 board에 거리 데이터를 덮어쓰고 있기 때문에, 0인 지점만 방문이 가능하고, 양수인 지점은 이미 방문한 곳, -1인 지점은 방문이 불가한 지점이므로, board가 0이 아니라면 넘어가야 하는 것이다.

이를 코드로 옮기면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int n, m;
int board[1001][1001];
queue<pair<int, int>> q;
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
            if (board[i][j] == 1) q.push({i, j});
        }
    }
    
    while (!q.empty()) {
        int x, y;
        tie(x, y) = q.front();
        q.pop();
        
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (board[nx][ny] != 0) continue;
            q.push({nx, ny});
            board[nx][ny] = board[x][y] + 1;
        }
    }
    
    int mx = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!board[i][j]) {
                cout << -1;
                exit(0);
            }
            mx = max(mx, board[i][j]);
        }
    }
    
    cout << mx - 1;
}