백준 2636번 치즈 C++

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

 

주어진 입력의 가장자리에는 치즈가 없기 때문에 (0, 0)에는 치즈가 절대 없을 것이다.

치즈가 전부 녹을 때까지 (0, 0)에서 bfs를 시작하여 치즈를 녹이는 것을 반복하였다.

 

bfs 도중에 치즈를 만나면 continue를 해서 바깥에 있는 치즈만 녹도록 하였다.

 

#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 <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int r, c;
int cheese_size = 0;
int last_size = 0;
int cnt = 0;

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

void bfs(vector<vector<bool>>& board) {
	vector<vector<bool>> found(r, vector<bool>(c, false));
	queue<pair<int, int>> q;
	q.push({ 0,0 });
	found[0][0] = true;
	while (!q.empty()) {
		auto curr = q.front();
		q.pop();
		if (board[curr.first][curr.second]) {
			cheese_size--;
			board[curr.first][curr.second] = false;
			continue;
		}
		for (int i = 0; i < 4; i++) {
			int nextRow = curr.first + dRow[i];
			int nextCol = curr.second + dCol[i];
			if (nextRow < 0 || nextRow >= r) continue;
			if (nextCol < 0 || nextCol >= c) continue;
			if (found[nextRow][nextCol]) continue;
			q.push({ nextRow,nextCol });
			found[nextRow][nextCol] = true;
		}
	}
}

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

	cin >> r >> c;
	vector<vector<bool>> board(r, vector<bool>(c));
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			int input;
			cin >> input;
			board[i][j] = input;
			if (board[i][j]) cheese_size++;
		}
	}
	last_size = cheese_size;
	while (cheese_size > 0) {
		last_size = cheese_size;
		bfs(board);
		cnt++;
	}
	cout << cnt << "\n" << last_size;
};