(C++) 백준 알고리즘 7576번 토마토

문제

풀이 (C++)

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
 
bool check[1003][1003] = {false,};
int dist[1003][1003];
int box[1003][1003];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0}; 
 
 
int main(){
    int M, N;
    int i,j;
    
    scanf("%d %d",&M,&N);
    
    for(i = 0; i< N; i++){
        for(j = 0; j<M; j++){
            scanf("%d", &box[i][j]);
        } 
    }
    
    queue< pair<int,int> > q;
    
    for(i = 0; i< N; i++){
        for(j = 0; j<M; j++){
            if(box[i][j] == 1){
                q.push(make_pair(i,j));
                dist[i][j] = 1;
                check[i][j] = true;
            }
        } 
    }        
    
    while (!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for (int k = 0; k<4; k++){
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0 <= nx && nx < N && 0 <= ny && ny < M){
                if(check[nx][ny] == false && box[nx][ny] != -1){
                    q.push(make_pair(nx, ny));
                    dist[nx][ny] = dist[x][y] + 1;
                    check[nx][ny] = true;
                }
            }
        }
    }
    
    for(i = 0; i< N; i++){
        for(j = 0; j<M; j++){
            if (box[i][j] == -1){
                dist[i][j] = 1;
            }
        }
    } 
    
    
    int max = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!dist[i][j]){
                printf("-1");
                return 0;
            }
            if (max < dist[i][j]){
                max = dist[i][j];
            }
        }
    }
    
    cout << max-1<< endl;
 
    
    return 0;
} 

문제 출처

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