[BOJ/백준 7576][C++] 토마토

문제

https://www.acmicpc.net/problem/7576

백준 7576

 

문제 내용

1은 익은 토마토를, 0은 아직 익지 않은 토마토를, -1을 토마토가 없는 칸을 뜻한다.

토마토는 인접한 토마토에게 영향을 받는데, 익은 토마토 옆의 익지 않은 토마토는 하루 뒤에 익게 된다.

토마토가 모두 익을 때까지의 최소 날짜를 출력하면 된다. (불가능한 경우 -1 출력)

 

문제 풀이

bfs로 문제를 풀면 된다.

단, 처음 시작할 때 1이었던 토마토들을 queue에 모두 넣은 상태로 돌려야 한다.

전부 익을 때까지 얼마나 걸리는지를 구하고 싶기 때문에, 이는 최단거리 문제라고 볼 수 있다. (거리는 아니지만 개념은 같다)

토마토 개수를 입력받을 때 세어둔 뒤에, bfs를 통해 익은 토마토를 체크하면서 -1 하고, 마지막에 cnt가 0인지 아닌지 체크하면 토마토가 모두 익었는지를 쉽게 체크할 수 있다.

 

코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

int bfs(queue<pair<int, int>> &que, vector<vector<int>> &arr, int cnt, int n, int m) {
    int time = 1;

    while (!que.empty()) {
        pair<int, int> tmp = que.front();
        que.pop();

        time = arr[tmp.first][tmp.second];
        for (int i = 0; i < 4; i++) {
            int nx = tmp.second + dx[i];
            int ny = tmp.first + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && arr[ny][nx] == 0) {
                que.push({ny, nx});
                arr[ny][nx] = time + 1;
                cnt--;
            }
        }
    }

    return (cnt == 0 ? time - 1 : -1);
}

int main() {
    int n, m;
    cin >> n >> m;

    int cnt = 0;
    vector<vector<int>> arr(m, vector<int>(n, 0));
    queue<pair<int, int>> que;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];

            if (arr[i][j] == 1) { // 익은 토마토
                que.push({i, j});
            } else if (arr[i][j] == 0) {
                cnt++;
            }
        }
    }

    cout << bfs(que, arr, cnt, n, m);
}