[백준] 2636 치즈

[백준] 2636 치즈

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

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

int N;
int M;
int board[101][101] = { 0 };

int dirR[4] = { 0, 0, 1, -1 };
int dirC[4] = { 1, -1, 0, 0 };

bool inRange(int r, int c) {
	if (r < 0 || r >= N) return false;
	if (c < 0 || c >= M) return false;
	return true;
}

//녹은 치즈조각 칸의 개수 반환
int meltCheese() {
	int visited[101][101] = { 0 };
	queue<pair<int, int>> q;
	q.push({ 0 ,0 });

	//녹을 치즈조각 칸의 좌표
	vector<pair<int, int>> melt;
    
	while (!q.empty()) {
		int curR = q.front().first; 
		int curC = q.front().second;
		q.pop();

		if (visited[curR][curC]) continue;
		visited[curR][curC] = 1;

		//공기와 인접한 치즈조각 칸
		if (board[curR][curC] == 1) {
			melt.push_back({ curR, curC });
			continue;
		}

		//공기 칸
		for (int d = 0; d < 4; ++d) {
			int nextR = curR + dirR[d];
			int nextC = curC + dirC[d];

			if (!inRange(nextR, nextC)) continue;
			if (visited[nextR][nextC]) continue;

			q.push({ nextR , nextC });
		}
	}

	for (int i = 0; i < melt.size(); ++i) {
		board[melt[i].first][melt[i].second] = 0;
	}
	return melt.size();
}

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

	cin >> N >> M;

	//맨 처음 치즈조각 칸의 개수
	int initialCheese = 0;

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

	//치즈조각이 녹기 전 치즈조각 칸의 개수
	int prev = initialCheese;
	//치즈조각이 녹은 후 치즈조각 칸의 개수
	int next;
	
	int time = 0;
	while (true) {
		next = prev - meltCheese();
		time++;
		//모든 치즈조각이 녹은 경우
		if (next == 0) {
			cout << time << "\n" << prev;
			break;
		}
		prev = next;
	}

	return 0;
}