[백준] 7576번: 토마토 /BFS

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

이 문제는 최단경로의 응용과 비슷하다. 익은 토마토가 1/ 안익은 토마토가 0 / 토마토가 없는 장소이면 -1 로 주어질 떄, 하루마다 익은 토마토 주위로 토마토가 익는다. 

이 문제의 핵심은

1. 초반의 익은 토마토의 위치를 x,y queue에 삽입해 놓을 것.

2. 큐를 두개 만들어 놓고 first큐에서 갈 수 있는 토마토의 위치(경로)에 1을 추가해준다. 그 추가된 경로를 second 큐에 삽입되고

하나의 사이클이 종료되면 일수를 하나 증가시킨다.

3. 예외적인 조건으로 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

move_tomato(); 를 통해서 한 사이클이 종료될 때, 다음 일수로 옮길 수 있는 토마토의 위치를 옮겨 넣는다. 

check변수는 모두 토마토로 채워져 있는 경우와 중복하여 일수를 계산하는 경우를 배제하기위한 변수로 사용한다.

#include<iostream>

#include<cstring>

using namespace std;

#include<queue>

int m, n;

int map[1001][1001];

int visit[1001][1001];

queue <int> qx;

queue <int> qy;

queue <int> second_qx;

queue <int> second_qy;

int days;

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

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

bool check = false;

bool isOkay(int xx, int yy)

{

if (xx > 0 && yy > 0 && xx <= m && yy <= n)

return true;

else

return false;

}

void move_tomato()

{

while (!second_qx.empty())

{

qx.push(second_qx.front());

second_qx.pop();

}

while (!second_qy.empty())

{

qy.push(second_qy.front());

second_qy.pop();

}

}

void bfs()

{

int x_temp, y_temp;

check = false;

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

{

x_temp = qx.front(); qx.pop();

y_temp = qy.front(); qy.pop();

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

{

int xx = x_temp + dx[j];

int yy = y_temp + dy[j];

if (isOkay(xx, yy) && !visit[xx][yy] && map[xx][yy] == 0 && map[xx][yy]!=-1)

{

visit[xx][yy] = true;

map[xx][yy] = 1;

second_qx.push(xx);

second_qy.push(yy);

check = true;

}

}

}

move_tomato();

}

int main()

{

cin >> n >> m;

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

{

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

{

cin >> map[i][j];

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

{

qx.push(i);

qy.push(j); //시작하기전 익은 토마토를 넣어두자.

}

else if(map[i][j]==0)

{

check = true; // 익어있지않는 것이 있을 떄(처음부터 모두 익었을 경우를 따질 때) 

}                  //즉, 익어있지않은 것이 있는 경우니까.

}

}

if (!check)

{

cout << "0" << endl;

return 0; // 모두 익어있을 경우 0을 출력하고 끝

}

check = false;

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

{

bfs();

if(check)

days++;

}

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

{

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

{

if (map[i][j] == 0)

{

cout << -1 << endl;

return 0;

}

}

}

cout << days << endl;

return 0;

}