7576 tomato

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

[7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net](https://www.acmicpc.net/problem/7576)

문제의 쟁점은 bfs 를 사용할수 있는가.

queue를 사용할 수 있는가 라고 판단했다.

여기서 나는 크게 1인 위치가 없어질때 까지를 판단하게 했고

자신이 1이면 상하 좌 우 를 보도록 하였다 이를 통해

한사이클 마다 익는 개수를 추가하고 체크한 녀석을 빼주는 방식으로

로직을 구현했다.

#include <iostream>
#include <queue>

using namespace std;

int    tomato[1000][1000];
int cnt = -1;
int n, m;

int mx[] = {0, 0, 1, -1};
int my[] = {-1, 1, 0, 0};

void solve(queue<vector<int>>& v)
{
    if (v.size() == 0) 
    {
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (tomato[i][j] == 0)
                {
                    cout << "-1"<<endl;
                    return ;
                }
            }
        } 
        cout << cnt << endl;
        return ;
    }
    int len = v.size();
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < 4; ++j) {
            vector<int> vp;
            vp = v.front();
            int _x = vp[0] + mx[j];
            int _y = vp[1] + my[j];
            if (_x >= 0 && _x < m && _y >= 0 && _y < n)
            {
                if (tomato[_x][_y] == 0) {
                    tomato[_x][_y] = 1;
                    vector<int> p;
                    p.push_back(_x);
                    p.push_back(_y);
                    v.push(p);
                }
            }
        }
        v.pop();
    }
    cnt++;
    solve(v);
}

int main()
{

    cin >> n >> m;
    queue<vector<int>> v;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin>>tomato[i][j];
            vector<int> p;
            if (tomato[i][j] == 1) {
                p.push_back(i);
                p.push_back(j);
                v.push(p);
            }
        }
    }
    solve(v);
    return 0;
}

나는 맛좋은 토마토가 먹고싶다..