백준 C++ 7576번) BFS - 토마토 관리

사용언어 : C++

 

 BFS 사용하여서, 해결하면 된다. 다만 여기서 주의할 점은 날짜별로 체크하기 때문에, q.size만큼 다 돌린후 날짜 + 1을 하였다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
#define MAXR 1001

vector<vector<int>> arr;
int visit[MAXR][MAXR] = { 0 };
int coun;
queue<pair<int, int>> q;
void BFS();
int check[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int N, M;

bool compare(int i, int j) {
	return j < i;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;

	for (int i = 0; i < M; ++i) {
		vector<int> num;
		int a;
		for (int j = 0; j < N; j++) {
			cin >> a;
			num.push_back(a);
			if (a == 1) {
				q.push(pair<int, int>(i, j));
				visit[i][j] = 1;
			}
			else if (a == -1)
				visit[i][j] = 1;
		}
		arr.push_back(num);
	}

	BFS();
	bool type = false;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (visit[i][j] == 0) {
				type = true;
				break;
			}
		}
		if (type)
			break;
	}
	if (type)
		cout << "-1" << "\n";
	else
		cout << coun-1 << "\n";
}
void BFS() {
	while (!q.empty()) {
		int n = q.size();
		for (int i = 0; i < n; i++) {
			pair<int, int> a = q.front();
			q.pop();
			for (int j = 0; j < 4; j++) {
				int ny = a.first + check[j][0];
				int nx = a.second + check[j][1];
				if ((nx >= 0 && nx < N) && (ny >= 0 && ny < M)){
					if (visit[ny][nx] == 0) {
						q.push(pair<int, int>(ny, nx));
						visit[ny][nx] = 1;
						arr[ny][nx] = 1;
					}
				}
			}
		}
		coun++;
	}
}