[BOJ] 7576 - 토마토 (C++)

문제

토마토

코드

#include <iostream>
#include <queue>

using namespace std;

int N, M, day = 0;
int box[1001][1001];
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
queue< pair<int, int> > q;

void bfs(){
    while (!q.empty()){
        int r = q.front().first, c = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++){
            int nr = r + dir[i][0], nc = c + dir[i][1];
            if (nr < 0 or nr >= M or nc < 0 or nc >= N) continue;
            if (box[nr][nc] == 0) {
                box[nr][nc] = box[r][c] + 1;
                day = max(day, box[nr][nc]);
                q.push(make_pair(nr,nc));
            }
        }
    }
}

bool check(){
    for (int i = 0; i < M; i++){
        for (int j = 0; j < N; j++){
            if (box[i][j] == 0) return false; 
        }
    }
    return true;
}

int main(void){
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> N >> M;
    for (int i = 0; i < M; i++){
        for (int j = 0; j < N; j++){
            cin >> box[i][j];
            if (box[i][j] == 1) q.push(make_pair(i,j));
        }
    }
    
    bfs();
    if (!check()) cout << -1;
    else day == 0 ? cout << day : cout << day-1;

    return 0;
}

접근

먼저 익은 토마토가 어디에 있는지 확인하는 것이 중요하다. 이를 위해서 전체를 순회해서 찾을 것인지, 익은 토마토만 따로 관리해 살펴볼 것인지가 시간초과를 나누는 부분인 것 같다. 따라서 큐에 익은 토마토만 넣어서 관리하면서 익어가는 날짜를 저장하고 큐가 빌 때까지 반복한다. 이후에도 익지 않은 토마토가 있다면 이때는 -1을 출력하고 그렇지 않은 경우 가장 늦게 익은 날짜를 출력해주면 된다. 단, 시작과 동시에 모든 토마토가 익어있을 수 있기 때문에 이때는 0이 잘 출력될 수 있게 확인해주어야 한다.