[C++] 백준 7576번 토마토

DFS, BFS문제입니다.

익은 토마토는 다음날 상, 하, 좌, 우의 토마토를 익게합니다. (익지 않은 토마토 제외)
이 때 토마토가 전부 익는데 걸리는 최소날짜를 구해야합니다.

숫자가 1인 부분을 큐에 넣어놓고 빼면서 주변이 0인곳을 탐색하는 방식으로
BFS를 사용하여서 문제를 풀었습니다.

0인곳을 탐색하면 그 위치를 큐에 넣고 방문을 했다고 처리해줍니다.
큐가 비어있게 되면은 배열에 0이 있는지 확인하고 없으면
카운트한 횟수를 출력하고, 있으면 -1을 출력합니다.

 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int map[1010][1010];
int moveX[4] = { 0, 1, 0, -1 };
int moveY[4] = { 1, 0, -1, 0 };
queue<pair<pair<int, int>, int> >q;

int main(int argc, char *argv[])
{
	int n, m;
	int a, b, c;
	int x, y;
	int flag = 0;

	memset(map, -1, sizeof(map));

	cin >> m >> n;

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> map[i][j];
			if (map[i][j] == 1) {
				q.push(make_pair(make_pair(i, j), 0));
			}
		}
	}

	while (!q.empty()) {
		a = q.front().first.first;
		b = q.front().first.second;
		c = q.front().second;
		q.pop();

		for (int i = 0; i < 4; ++i) {
			x = a + moveX[i];
			y = b + moveY[i];

			if (map[x][y] == 0) {
				q.push(make_pair(make_pair(x, y), c + 1));
				map[x][y] = 1;
			}
		}
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (map[i][j] == 0) {
				flag = 1;
			}
		}
	}

	if (flag) {
		cout << "-1" << endl;
	}
	else {
		cout << c << endl;
	}

	return 0;
}