백준 7576 토마토 - C++

 

접근

입력이 주어졌을 때 익은 토마토를 전부 q에 넣고 bfs 탐색을 시작한다. 

만약 아직 익지 않은 토마토가 있다면 출력은 -1 

그렇지 않다면 모든 토마토가 익는데 걸린 시간 출력

 

#include <iostream>
#include <queue>
using namespace std;
int A[1001][1001];
int check[1001][1001];
int low[] = {-1, +1, 0, 0};
int col[] = {0, 0, -1, +1};
int M, N;

int bfs(){
    queue<pair<int, int>> q;
    // 익은 토마토 찾아서 q에 넣기
    for(int i=1; i<=N; i++){
        for( int j=1; j<=M; j++){
            if( A[i][j] == 1){
                check[i][j] == 0;
                q.push(make_pair(i,j));
                
            } else{
                check[i][j] = -1;
            }
            
        }
    }
    int curI, curJ;
    while(!q.empty()){
        curI = q.front().first;
        curJ = q.front().second;
        q.pop();
        //상하좌우 총 4번 비교
        for(int i=0; i<4; i++){
            int valI = curI+low[i];
            int valJ = curJ+col[i];
            if( ( valI >= 1 && valI <= N ) && ( valJ >= 1 && valJ <= M ) ){ 
                if(A[valI][valJ] == 0 && check[valI][valJ] == -1){
                    q.push(make_pair(valI,valJ));
                    check[valI][valJ] = check[curI][curJ]+1;
                } 
            }
        }
    }
    int result = check[curI][curJ];
    return result > 0 ? result : 0;
}

int main()
{   
    cin >> M >> N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            cin >> A[i][j];
        }
    }

    int cnt = bfs();
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            if(A[i][j] == 0 && check[i][j] == -1) cnt = -1;
        }
    }
    cout << cnt;
    return 0;
}

 

간소화 version

#include <iostream>
#include <queue>
using namespace std;
int A[1001][1001];
int low[] = {-1, +1, 0, 0};
int col[] = {0, 0, -1, +1};
int M, N;

int bfs(){
    queue<pair<int, int>> q;
    // 익은 토마토 찾아서 q에 넣기
    for(int i=1; i<=N; i++){
        for( int j=1; j<=M; j++){
            if( A[i][j] == 1){
                q.push(make_pair(i,j));
            } 
        }
    }
    int curI, curJ;
    while(!q.empty()){
        curI = q.front().first;
        curJ = q.front().second;
        q.pop();
        //상하좌우 총 4번 비교
        for(int i=0; i<4; i++){
            int valI = curI+low[i];
            int valJ = curJ+col[i];
            if( ( valI >= 1 && valI <= N)  && (valJ >=1 && valJ <= M)  ){ 
                if(A[valI][valJ] == 0 ){
                    q.push(make_pair(valI,valJ));
                    A[valI][valJ] = A[curI][curJ]+1;
                } 
            }
        }
    }
    int result = A[curI][curJ];
    return result > 1 ? result-1 : 0;
}

int main()
{   
    cin >> M >> N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            cin >> A[i][j];
        }
    }

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