[백준 00000] 치즈 (C++)

 

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>

#define F first
#define S second
#define IN(Y, X) Y >=0 && Y < N && X >=0 && X < M

using namespace std;

int N, M, cheese, board[100][100];
bool visit[100][100];
queue<pair<int, int>> q;
vector<pair<int, int>> melt;

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


void BFS(int y, int x) {
	visit[y][x] = true;
	q.push({ y, x });

	while (!q.empty()) {
		pair<int, int> front = { q.front().F, q.front().S };
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = front.F + dy[i];
			int nx = front.S + dx[i];
			if (IN(ny, nx) && !visit[ny][nx]) {
				if (!board[ny][nx]) {
					q.push({ ny, nx });
					visit[ny][nx] = true;
				}
				else board[ny][nx]++;
				//공기와 닿은 면적이 2 이상이면 녹이기 위해 좌표 저장해두기
				if (board[ny][nx] >= 3) {
					melt.push_back({ ny, nx });
					visit[ny][nx] = true;
				}
			}
		}
	}
}

int solve() {
	int t = 0;	
	while (cheese) {
		//탐색하고
		BFS(0, 0);
		//녹이고
		cheese -= melt.size();  //cheese 크기 제거
		while (!melt.empty()) {
			board[melt.back().F][melt.back().S] = 0;
			melt.pop_back();
		}
		//다음 탐색을 위하여 값들 초기화해주기
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] >= 2) board[i][j] = 1;
			}
		}
		memset(visit, 0, sizeof(visit));
		t++;
	}
	return t;
}

int main(void) {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];
			if (board[i][j]) cheese++;
		}
	}
	cout << solve();
}