[백준]Baekjoon7576(BFS)

문제 링크 : https://www.acmicpc.net/problem/7576

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

using namespace std;

int arr[1000][1000];

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
 
int N, M;
int result;
void BFS(queue<pair<int,int>> *q)
{
	result = 1; //가장 마지막 날을 저장하기 위한 변수
	while (!(*q).empty()){
		int x = (*q).front().first;
		int y = (*q).front().second;
		(*q).pop();
		
		for (int i = 0; i < 4; i++) { //for문이 한번 돌 때마다 아직 익지 않은 인접 토마토 값이 원래 토마토 좌표 + 1이 되도록 한다.
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < N && ny >= 0 && ny < M) { 
				if (arr[nx][ny] == 0) {
					arr[nx][ny] = arr[x][y]+1;
					(*q).push(make_pair(nx, ny));
					if (arr[nx][ny] > result)
						result = arr[nx][ny]; //가장 값이 큰 것이 마지막 날에 익은 것이므로 저장
				}
			}
		}
	}
}
int main()
{
	scanf("%d %d", &M, &N);

	queue<pair<int, int>> q;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &arr[i][j]);
			if (arr[i][j] == 1)
				q.push(make_pair(i, j)); //값이 1인 토마토 인접 토마토부터 익기 시작하므로 큐에 미리 넣어준다.
		}
	}
	BFS(&q); // 매개변수로 값이 1인 좌표가 저장되어있는 큐 전달
	bool b = true;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (arr[i][j] == 0) { //만약 배열 값중 하나라도 0이라면 break
				b = false;
				break;
			}
		}
		if (!b) break;
	}
	if (b) printf("%d\n",result-1);
	else printf("-1\n");
}