백준 2638번 치즈 C++

출처 : https://www.acmicpc.net/problem/2638

 

가장자리에는 치즈가 놓이지 않기 때문에 0,0에서 빈 공간을 bfs로 탐색하면서 바깥쪽 공기를 검사한 뒤 치즈가 바깥쪽 공기와 2개의 면 이상 닿아있다면 녹도록 했다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, m;

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

vector<vector<int>> board;
vector<vector<bool>> visited;
vector<vector<bool>> isOut;

void Refresh() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visited[i][j] = false;
			isOut[i][j] = false;
		}
	}
}

void BfsCheckOut() {
	queue<pair<int, int>> q;
	q.push({ 0,0 });
	visited[0][0] = true;
	isOut[0][0] = true;

	while (!q.empty()) {
		auto curr = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nextRow = curr.first + dRow[i];
			int nextCol = curr.second + dCol[i];
			if (nextRow < 0 || nextRow >= n) continue;
			if (nextCol < 0 || nextCol >= m) continue;
			if (board[nextRow][nextCol] == 1) continue;
			if (visited[nextRow][nextCol]) continue;
			visited[nextRow][nextCol] = true;
			isOut[nextRow][nextCol] = true;
			q.push({ nextRow,nextCol });
		}
	}
}

bool CheckCheese(int row, int col) {
	int contectAir = 0;
	for (int i = 0; i < 4; i++) {
		int nextRow = row + dRow[i];
		int nextCol = col + dCol[i];
		if (board[nextRow][nextCol] == 1) continue;
		if (!isOut[nextRow][nextCol]) continue;
		contectAir++;
	}
	if (contectAir >= 2) return true;
	return false;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	board = vector<vector<int>>(n, vector<int>(m));
	visited = vector<vector<bool>>(n, vector<bool>(m, false));
	isOut = vector<vector<bool>>(n, vector<bool>(m, false));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
		}
	}
	int ans = 0;
	while (true) {
		Refresh();
		BfsCheckOut();
		bool isCheeseExsist = false;
		vector<pair<int, int>> meltCheeses;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (board[i][j] == 0) continue;
				isCheeseExsist = true;
				if (CheckCheese(i, j))
					meltCheeses.push_back({ i,j });
			}
		}
		if (!isCheeseExsist) break;
		for (auto cheese : meltCheeses) {
			int row = cheese.first;
			int col = cheese.second;
			board[row][col] = 0;
		}
		ans++;
	}
	cout << ans;
};