언제나 처음처럼

[문제 링크]

간단해보이지만 함정이 하나 있는 문제였다.

치즈가 공기와 접촉하는지 확인하기 위해 치즈 기준 동서남북 방향에 0이 있는지 체크하고 0이 두군데 이상 있다면 공기와 접촉하고 있다고 단정 지을 수 있는데, 치즈로 둘러 쌓인 내부의 0은 공기가 통하지 않기 때문에 이를 제외시켜줘야 한다.

따라서, 치즈를 녹이기 전에 {0, 0} 좌표를 시작으로 BFS를 수행하여 실제로 공기가 통하는 좌표를 먼저 마킹했다.

그 다음 전체 판을 탐색하여 공기와 접해있는 면이 2개 이상인 치즈를 녹이는 방식으로 구현하였다.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int N, M, cheezeCnt = 0;
int board[101][101];
bool isAir[101][101];

int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };

void markingAir() {
	queue<pair<int, int>> q;
	memset(isAir, false, sizeof(isAir));

	q.push({ 0,0 });
	isAir[0][0] = true;

	while (!q.empty()) {
		int hereY = q.front().first;
		int hereX = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nearY = hereY + dy[i];
			int nearX = hereX + dx[i];
			if (nearY >= 0 && nearY < N && nearX >= 0 && nearX < M) {
				if (board[nearY][nearX] == 0 && !isAir[nearY][nearX]) {
					q.push({ nearY, nearX });
					isAir[nearY][nearX] = true;
				}
			}
		}
	}
}

void meltCheeze() {
	int temp[101][101];

	memcpy(temp, board, sizeof(board));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (temp[i][j] == 1) {
				int air = 0;

				for (int k = 0; k < 4; k++) {
					int nearY = i + dy[k];
					int nearX = j + dx[k];
					if (isAir[nearY][nearX])
						air++;
				}

				if (air >= 2) {
					board[i][j] = 0;
					cheezeCnt--;
				}
			}
		}
	}
}

int getAllMeltCheezeTime() {
	int time = 0;

	while (cheezeCnt) {
		markingAir();
		meltCheeze();
		time++;
	}

	return time;
}

int main(void) {
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			int n;
			cin >> n;
			board[i][j] = n;
			if (board[i][j] == 1)
				cheezeCnt++;
		}

	cout << getAllMeltCheezeTime() << endl;

	return 0;
}