[C++] 7576 - 토마토

문제 링크 : https://www.acmicpc.net/problem/7576

7576번: 토마토

 

토마토가 들어있는 칸을 먼저 기본 Queue에 넣어주고 나서

그 칸부터 상하좌우에 빈 공간이 있으면 그 공간에 값을 넣어주고 그 좌표를 또다시 Queue에 넣어 

반복하도록 만들었다.

 

모든 탐색이 끝나고 배열 안에 0이 존재한다면 그것은 토마토가 전부 익지 못하는 상황이므로 -1을 출력하고

만약 0이 없다면 최댓값에서 1을 뺀 값을 출력했다.

 

입력을 받을때 모든 칸이 -1일 경우?에는 토마토가 없는 상황인지라 0을 출력해야할지 -1을 출력해야할지 고민을 하다고 그냥 0을 출력하도록 했다.

 

 

 

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
 
typedef pair<int, int> pii;
 
queue<pii> q;
 
int B[1005][1005];
int N, M;
 
void BFS()
{
    int X[4] = {0, 0, 1, -1};
    int Y[4] = {1, -1, 0, 0};
 
    while(!q.empty())
    {
        pii p = q.front();
        q.pop();
        for(int i = 0; i < 4; ++i)
        {
            int NX = p.second + X[i];
            int NY = p.first+ Y[i];
 
            if(0 <= NY && NY < N && 0 <= NX && NX < M)
            {
                if(B[NY][NX] != -1 && !B[NY][NX])
                {
                    B[NY][NX] = B[p.first][p.second] + 1;
                    q.push(pii(NY, NX));
                }
            }
        }
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> M >> N;
 
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < M; ++j)
        {
            cin >> B[i][j];
            if(B[i][j] == 1)
                q.push(pii(i,j));
        }
    }
    if(!q.empty())
        BFS();
    else
    {
        cout << -1 << endl;
        return 0;
    }
 
    int MAX = 0;
    int flag = 0;
 
    for(int i = 0;!flag && i < N; ++i)
    {
        for(int j = 0;!flag && j < M; ++j)
        {
            if(B[i][j] == 0)
                flag = 1;
            if(MAX < B[i][j])
                MAX = B[i][j];
        }
    }
 
    if(flag)
        cout << -1 << endl;
    else if(MAX == 0)
        cout << 0 << endl;
    else
        cout << MAX-1 << endl;
 
    return 0;
}