빙산

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

using namespace std;

int n, m; //입력 받기
int a[301][301]; // a의 개수 
bool d[301][301]; // 이동할지 말지결정하기
int x[301][301]; // 나중에 빙산깎을때 필요함
int g = 0; // 빙산이 다깎였는지 확인하기 다깎였으면 n*m 이 g랑 같을듯
bool ge = false; //빙산이 다깎였으면 true로
int dx[] = { 0,0,1,-1 };//이동방향!
int dy[] = { 1,-1,0,0 };//이동방향임

int bfs() {
	queue<pair<int, int>> q;
	int x = 0 , y = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++) {
			if (a[i][j] != 0) {
				x = i; y = j;
				break;
			}
		}
	}
	d[x][y] = true;
	q.push(make_pair(x, y));
	int sum = 1;
	while (!q.empty())
	{
		x = q.front().first; y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i]; int ny = y + dy[i];
			if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
				if (a[nx][ny] != 0 && d[nx][ny] == false) {
					d[nx][ny] = true;
					q.push(make_pair(nx, ny));
				}
			}
		}
		if (q.empty()) {//q다쓰고나서 .. 또 쓸 애가있으면 다시 push해주고 다시 루프
			
			for (int i = 1; i <= n; i++)
			{
				for (int j = 1; j <= m; j++) {
					if (a[i][j] != 0 && d[i][j] == false) {
						sum += 1;
						int a = i, b = j;
						q.push(make_pair(a, b));
						d[a][b] = true;
						break;
					}
				}
			}
		}
	}
	return sum;
}
void year() {//만약에.. 1년지나면 빙산깎기용 x초기화 해주면서, 빙산이 다깎였는지 확인하기
	for(int i = 1; i<= n; i++){
		for (int j = 1; j <= m; j++)
		{
			x[i][j] = 0;
			if (a[i][j] == 0)
				g += 1;
		}
	}
	if (g == n * m)
		ge = true;
	else
		g = 0;

}
int main() {
	cin >> n >> m;
	vector<pair<int, int>> xy;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			scanf("%d", &a[i][j]);
			if (a[i][j] != 0)
				xy.push_back(make_pair(i, j));
		}
	}
	int result = bfs();
	int years = 0; bool go = false;
	while (result == 1) {
		years += 1;
		year();
        // 빙산 깎기
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (a[i][j] != 0) {
					for (int k = 0; k < 4; k++) {
						int nx = i + dx[k]; int ny = j + dy[k];
						if (a[nx][ny] == 0) {
							x[i][j] += 1;
						}
					}
				}
				d[i][j] = false;
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				a[i][j] -= x[i][j];
				if (a[i][j] < 0) {
					a[i][j] = 0;
				}
			}
		}
        //다깎였는지... 깎였으면 루프탈출!
		if (ge == true) {
			go = true;
			break;
		}
		result = bfs();
	}
	if (go) cout << 0 << endl;
	else
	cout << years << endl;

	return 0;
}

/*
전체적으로 조금 조잡한 상태인듯하다. 졸린상태에서 해서그런지는 잘모르겠으나
하면서도 이렇게해도 되나? 라는 생각이 조금많이 든거같다.
for 3중 루프까지 써서 deepth가 너무깊지 않나생각이드는데 해결했으니뭐...

*/

쉬운 BFS문제