[백준] 7576번: 토마토 / BFS depth(cycle)

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

기존의 bfs의 depth + cycle수행 결과의 알고리즘이다. 

#include<iostream>

using namespace std;

#include<queue>

int n, m,tomato[1050][1050],day;

bool visited[1050][1050];

queue <int> qx;

queue <int> qy;

int xx[4] = { 0,-1,0,1 };

int yy[4] = { 1,0,-1,0 };

void bfs()

{

while (!qx.empty() & !qy.empty())

{

int cycle = qx.size();

for (int j = 0; j < cycle; j++)

{

int tmp1 = qx.front(); qx.pop();

int tmp2 = qy.front(); qy.pop();

visited[tmp1][tmp2] = true;

for (int i = 0; i < 4; i++)

{

int nx = tmp1+ xx[i];

int ny = tmp2 + yy[i];

if (nx > 0 && ny > 0 && nx <= m && ny <= n)

{

if (!visited[nx][ny] && tomato[nx][ny]==0)

{

tomato[nx][ny] = 1;

visited[nx][ny] = true;

qx.push(nx);

qy.push(ny);

}

}

}

}

day++;

}

}

int main()

{

cin >> n >> m;

for (int i = 1; i <= m; i++)

{

for (int j = 1; j <= n; j++)

{

cin >> tomato[i][j];

if (tomato[i][j] == 1)

{

qx.push(i);

qy.push(j);

}

}

}

bfs();

bool valid = true;

for (int i = 1; i <= m; i++)

{

for (int j = 1; j <= n; j++)

{

if (!visited[i][j] && tomato[i][j]!=-1)

{

valid = false;

}

}

}

if (valid)

cout << day-1 << "\n";

else

cout << "-1" << "\n";

return 0;

}