greentea31's Note

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

풀이 과정

하루가 지날 때마다 근처에 있는 토마토가 익을 때, 모든 토마토가 익는데 며칠이 걸리는지 구하는 문제이다.

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84

큐로 flood-fill을 구현하는 일종의 bfs 문제이다. board에 토마토가 익는데 걸리는 날짜가 저장되어 있다고 생각하고, flood-fill로 주변 토마토를 익혀가면서 주변 토마토의 board값을 기존 토마토의 board값 + 1을 시켜주면서 모든 토마토를 익힌다.

bfs 과정이 끝나면 board를 다 살펴보면서 0이 있으면 익지 않은 토마토가 존재하므로 -1, 0이 없으면 board의 최댓값의 -1을 답으로 출력해주면 된다. board값이 1로 주어진 토마토는 주어진 즉시, 0일째에 이미 익은 토마토이지만 1일째 익은 것으로 인식되므로 모든 토마토의 익은 날짜가 1씩 더해져 있기 때문 출력 전 -1을 해주는 것이다.

시작점이 여러 곳인 bfs는 그냥 bfs의 시작시에 큐에 여러 점을 넣어주고 돌리면 된다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;

int board[1001][1001];
int M, N;

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

void bfs() {
    queue<pair<int, int>> Q;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 1) Q.push(make_pair(i, j));
        }
    }

    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = cur.second + dx[i];
            int ny = cur.first + dy[i];
            if (0 <= nx && nx < M && 0 <= ny && ny < N) {
                if (board[ny][nx] == 0) {
                    board[ny][nx] = board[cur.first][cur.second] + 1;
                    Q.push(make_pair(ny, nx));
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> M >> N;
    int num;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> num;
            board[i][j] = num;
        }
    }

    bfs();

    int answer = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 0) {
                cout << -1;
                return 0;
            }

            if (board[i][j] > answer) {
                answer = board[i][j];
            }
        }
    }

    cout << answer-1;

    return 0;
}