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

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

7576번: 토마토

#include<iostream>
#include<queue>
#include<utility>
#include<vector>

using namespace std;

int M, N;
int direct[4][2] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };
vector<vector<int>> Tomato;
queue<pair<int, int>> Q;

void BFS() {
	while (!Q.empty()) {
		pair<int, int> know = Q.front();
		Q.pop();

		for (int i = 0; i < 4; i++) {
			int n = know.first + direct[i][0];
			int m = know.second + direct[i][1];

			if (0 <= n && n < N && 0 <= m && m < M &&Tomato[n][m] != -1) {
				if (Tomato[n][m] == 0 || Tomato[n][m] > Tomato[know.first][know.second] + 1) {
					Q.push(make_pair(n, m));
					Tomato[n][m] = Tomato[know.first][know.second] + 1;
				}
			}
		}
	}
}

int main(void) {
	//입력
	cin >> M >> N;

	for (int i = 0; i < N; i++) {
		vector<int> temp;
		for (int j = 0; j < M; j++) {
			int x;
			cin >> x;
			temp.push_back(x);
		}
		Tomato.push_back(temp);
	}

	//BFS 호출
	for (int i = 0; i < Tomato.size(); i++) {
		for (int j = 0; j < Tomato[i].size(); j++) {
			if (Tomato[i][j] == 1)
				Q.push(make_pair(i, j));
		}
	}
	BFS();

	//정답출력
	int max = 0;

	for (int i = 0; i < Tomato.size(); i++) {
		for (int j = 0; j < Tomato[i].size(); j++) {
			if (Tomato[i][j] > max)
				max = Tomato[i][j];
			if (Tomato[i][j] == 0) {
				cout << -1 << endl;
				return 0;
			}
		}
	}

	if (max == 1)
		cout << 0 << endl;
	else
		cout << max - 1 << endl;

}