89. 토마토(BFS 활용) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★★

#include <stdio.h>
#include <queue>

using namespace std;

int a[1000][1000];
int dis[1000][1000];

struct Tom
{
	int x;
	int y;
	Tom(int x, int y)
	{
		this -> x = x;
		this -> y = y;
	}
};

int main()
{
	int m, n, res = 0;
	bool flag = true;
	
	int dx[4] = {-1, 0, 1, 0};
	int dy[4] = {0, -1, 0, 1};
	
	scanf("%d %d", &m, &n); // m과 n을 읽는 순서를 조심하자!!!
	queue<Tom> Q;
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			scanf("%d", &a[i][j]);
			
			if(a[i][j] == 1)
				Q.push(Tom(i, j));
		}
	}
	
	while(!Q.empty())
	{
		Tom temp = Q.front();
		Q.pop();
		
		int x = temp.x;
		int y = temp.y;
		
		for(int i = 0; i < 4; i++)
		{
			if(a[x+dx[i]][y+dy[i]] == 0)
			{
				if(x+dx[i] >= 1 && x+dx[i] <= n && y+dy[i] >= 1 && y+dy[i] <= m)
				{
					a[x+dx[i]][y+dy[i]] = 1;
					dis[x+dx[i]][y+dy[i]] = dis[x][y] + 1;
					Q.push(Tom(x+dx[i], y+dy[i]));
				}
			}
		}
	}
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(res < dis[i][j])
				res = dis[i][j];
			
			else if(a[i][j] == 0)
				flag = false;
		}
	}
	
	if(flag)
		printf("%d", res);
	else
		printf("-1");
		
	return 0;
}