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

🔍 문제 해결 방법

먼저 익은 토마토는 모두 큐에 넣어 놓는다.

이후 BFS로 탐색을 하면서, 익은 토마토와 인접한 토마토 중 아직 안 익은 토마토(0)가 있으면,

익은 토마토와 인접한 토마토는 하루 지난 후 익게 되므로 익은 토마토와 인접한 토마토 = 익은 토마토 익은 날 + 1 를 한다. 

이후 익은 토마토를 큐에 넣어서 다음 인접한 토마토 중 안 익은 토마토를 구한다.

main 함수로 리턴 후, 익은 토마토는 모두 1 이상의 값을 가지므로 하나라도 0인 토마토가 있으면 -1을 출력하고 리턴한다.

없다면, 모든 익은 토마토 중 가장 마지막에 익은 토마토에 있는 값을 출력하여 모든 토마토가 익을 수 있는 최소 날짜를 구한다.

 

🔍 DoubleFree 오류 문제 해결

사소한 실수로 인해..

int search() 했는데 리턴을 안 해서 발생했다.

void search()로 바꿔서 해결.

 

💻 제출 코드

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

using namespace std;

int M,N;
int nx[] = {1,0,-1,0};
int ny[] = {0,1,0,-1};

void search(queue< pair<int,int> > &q, vector< vector<int> > &tomato){

    while(!q.empty()){
        int cx = q.front().first;
        int cy = q.front().second;
        //cout << "visit (" << cx << "," << cy << "):" << tomato[cx][cy] << endl;
        q.pop();
        for(int i=0; i<4; i++){
            int next_x = cx + nx[i];
            int next_y = cy + ny[i];
            if(next_x < 0 || next_y < 0 || next_x >= N || next_y >= M) continue;
            if(tomato[next_x][next_y] == 0){
                // (cx,cy)와 인접한 토마트는 (cx,cy)익은 날짜+1에 익게 됨
                tomato[next_x][next_y] = tomato[cx][cy]+1;
                //cout << "visit (" << next_x << "," << next_y << "):" << tomato[next_x][next_y] << endl;
                q.push(make_pair(next_x,next_y));
            }
        }
    }
}

int main(){
    int max=0;
    cin >> M >> N;
    
    queue< pair<int, int> > q;
    vector< vector<int> > tomato(N, vector<int>(M,0));

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> tomato[i][j];
            if(tomato[i][j]==1){ // 익은 토마토를 모두 큐에 넣음
                q.push(make_pair(i,j));
            }
        }
    }
    // BFS으로 탐색
    search(q,tomato);

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(tomato[i][j] == 0) {
                // 안 익은 토마토 하나라도 있으면 -1 출력 후 리턴
                cout << "-1" << endl;
                return 0;
            }
            // 모든 토마토 익는데 걸리는 시간 구하기 위해
            if(tomato[i][j] > max) max = tomato[i][j];
        }
    }
    // 처음 익은 토마토 인근 토마토의 익는 날짜가 1이 아닌 익은토마토(1)+1로 계산되었으므로 1을 빼줌
    cout << max-1 << endl;

    return 0;
}