백준 2636번 : 치즈 BFS C++

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

2636번: 치즈

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[103][103], ans;
queue<pair<int, int> > Q;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };


// 1. 공기 구역 BFS
// 2. 공기와 접한 치즈 사라짐
// 1, 2 반복 
bool air[103][103];
queue<pair<int, int> > airQ;


void air_spread() {
	while (!airQ.empty()) {
		int x = airQ.front().first;
		int y = airQ.front().second;
		airQ.pop();

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

			if (nx < 0 || nx >= n || ny < 0 || ny >= m || air[nx][ny] == 1) continue;
			if (arr[nx][ny] == 0) {
				airQ.push({ nx,ny });
				air[nx][ny] = 1;
			}
		}
	}
}


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 >> arr[i][j];
			if (arr[i][j] == 1) {
				Q.push({ i,j });
			}
		}
	}

	// 맨 처음 공기인 부분 
	for (int i = 0; i < n; i++) {
		air[i][0] = 1;
		airQ.push({ i,0 });
		air[i][m - 1] = 1;
		airQ.push({ i,m - 1 });
	}

	for (int i = 0; i < m; i++) {
		air[0][i] = 1;
		airQ.push({ 0,i });
		air[n-1][i] = 1;
		airQ.push({ n-1, i});
	}


	int t = Q.size();
	while (!Q.empty()) {
		air_spread();
		t = Q.size();
		vector<pair<int, int> > melt;

		for (int q = 0; q < t; q++) {
			int x = Q.front().first;
			int y = Q.front().second;
			Q.pop();

			bool has_hole = false;
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
				if (air[nx][ny] == 1) {
					melt.push_back({ x,y });
					has_hole = true;
					break;
				}
			}
			if (!has_hole) Q.push({ x,y });
		}

		for (int i = 0; i < melt.size(); i++) {
			arr[melt[i].first][melt[i].second] = 0;
			air[melt[i].first][melt[i].second] = 1;
			airQ.push({ melt[i].first, melt[i].second });
		}
		ans++;
	}

	cout << ans << '\n';
	cout << t << '\n';
	return 0;
}

백준 2636번