(C++) 백준 7576번 - 토마토

문제 링크 : https://www.acmicpc.net/problem/7576

7576번: 토마토

풀이

BFS를 이용한 거리 문제와 비슷하게 풀이하면 된다.

거리를 토마토가 익는 데 걸리는 시간의 길이라고 생각하고 풀면 어렵지 않게 해결할 수 있다.

문제 해결 시 중요한 점은 시작점이 될 수 있는 후보들, 즉 익은 토마토들의 위치를 먼저 파악 후에 이들을 Queue에 넣고 시작해야 한다는 점이다.

#include <iostream>
#include <queue>
#include <utility>
#define X first
#define Y second

using namespace std;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int brd[1002][1002];
int dist[1002][1002];
queue<pair<int,int>> Q;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  

    int n, m;
    cin >> m >> n;
    
    int cnt = 0; // 익지 않은 토마토의 수
    for(int i = 0; i < n; i++){ // 토마토 저장
        for(int j = 0; j < m; j++){
            int tomato;
            cin >> tomato;
            if(tomato == 0) cnt++; // 익지 않은 토마토의 개수 파악
            if(tomato == 1) { // 익은 토마토의 위치 파악
                Q.emplace(i, j); // 익은 토마토부터 계산 시작하기 위해 큐에 넣기
                dist[i][j] = 1; // 0일차부터 익어있음(마지막 출력시 -1 할 것)
            }
            brd[i][j] = tomato;
        }
    }
    if(cnt == 0){
        cout << 0;
        return 0;
    }

    while(!Q.empty()){ // 익는데 걸리는 시간을 거리로 생각하여 dist에 저장
        auto cur = Q.front();
        int prev = dist[cur.X][cur.Y]; // 현재 몇 일째인지
        for(int i = 0; i < 4; i++){
            int x = cur.X + dx[i];
            int y = cur.Y + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m){ // 유효성 검사
                if(brd[x][y] != -1 && dist[x][y] == 0){ // 해당 칸에 토마토가 없지 않고, 몇 일차에 익을지 계산된 적이 없다면 계산을 시작
                    Q.emplace(x, y); // 다음 날에 익을 토마토의 칸을 큐에 저장
                    dist[x][y] = prev + 1; // 다음 날에 해당 칸의 토마토는 익음
                }
            }
        }
        Q.pop();
    }

    int mx = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(dist[i][j] == 0 && brd[i][j] != -1) { // 익지 않은 토마토가 있다면 (날짜 계산이 되지 않았지만 칸에 토마토가 있을 때)
                cout << -1;
                return 0;
            }
            mx = max(mx, dist[i][j]);
        }
    }
    cout << mx-1;
}