백준 2638 치즈

백준 2638
가장자리에 치즈가 놓이지 않아서 괜찮았던 문제
bfs(0,0)을 돌려서 외부 공기층을 vis[i][j] = 2로 만들고
치즈 상하좌우에 2가 2개이상 있는지 확인하면 끝나는 문제

#include<bits/stdc++.h>
using namespace std;
#define INF 987654321
int n, m;
int vis[101][101];
int board[101][101];
int board1[101][101];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
queue<pair<int, int>> q;
int ans;
void bfs() {
	q.push({ 0,0 });
	vis[0][0] = 2;

	while (!q.empty()) {

		auto cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {

			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];

			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

			if (!vis[nx][ny] && !board[nx][ny]) {
				q.push({ nx,ny });
				vis[nx][ny] = 2;
			}
		}

	}

}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n >> m;
	

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			board1[i][j] = board[i][j];
		}
	}

	while (1) {

		int flag = 0;

		bfs();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (board[i][j] == 1) {
					
					int cnt = 0;

					for (int t = 0; t < 4; t++) {
						int nx = i + dx[t];
						int ny = j + dy[t];

						if (vis[nx][ny] == 2) cnt++;
					}

					if (cnt >= 2) {
						board1[i][j] = 0;
					}
				}
			}
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				board[i][j] = board1[i][j];
				if (board[i][j] == 1) flag = 1;
			}
		}
		ans++;

		if (!flag) break;
		
		memset(vis, 0, sizeof(vis));

	}
	cout << ans << '\n';
}