백준 7576: 토마토

토마토문제 bfs를 사용하면 되는 문제이다. bfs의 개념을 알면 쉽게 풀 수 있으나 주의해야할 부분이 있다면 토마토가 있는 부분을 모두 동시에 큐에 넣어줘야한다는 것. 토마토가 익지 못하는 경우를 판단해줘야 한다는 것 정도다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<vector<int>> a (1002);
int g_c;
int g_r;
int check[1005][1005];
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
bool no_tomato = false;
int main()
{
    cin >> g_c >> g_r;
    for (int i = 0;i < g_r; ++i)
    for (int j = 0; j < g_c; ++j)
    {
        int input;
        cin >> input;
        a[i].push_back(input);
    }
    queue<pair<int, int>> q;
    for (int i = 0; i < g_r; ++i)
    for (int j = 0; j < g_c; ++j)
    {
        if (a[i][j] == 1)
        {
            q.push(make_pair(i, j));
            check[i][j] = 1;
        }
    }
 
    while (!q.empty())
    {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        for (int k = 0; k < 4; ++k)
        {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if (nr >= 0 && nr < g_r && nc >= 0 && nc < g_c)
            if (a[nr][nc] == 0 && check[nr][nc] == 0)
            {
                check[nr][nc] = check[r][c] + 1;
                q.push(make_pair(nr,nc));
            }
        }
    }
    int max_val = 0;
    for (int i = 0; i < g_r; ++i)
    for (int j = 0; j < g_c; ++j)
    {
        max_val = max(max_val, check[i][j]);
        if (check[i][j] == 0 && a[i][j] == 0)
            no_tomato = true;
    }
    if (no_tomato == true)
    {
        cout << -1 << endl;
        return 0;
    }
    cout << max_val  - 1 << endl;
    return 0;
}