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

문제 링크: https://www.acmicpc.net/problem/2636

2636번: 치즈

1. 주의할 점

- 종료가 될 경우, 직전상태의 치즈 개수를 알고 있어야 한다

- 치즈 내부의 구멍은 외부와 연결되지 않는 한, 공기가 통하지 않는다고 가정한다

 

2. 구현

- Cal() 함수는 남아있는 치즈의 개수를 확인하는 함수로, 현재 치즈가 남아있다면 남아 있는 개수를 저장하고, 남아 있지 않다면 Finish를 True로 갱신하여 끝나도록 한다.

- Find_uncheck() 함수는 현재 외부 공기를 큐에 담는다

- Spread() 함수는 외부 공기와 접촉한 치즈를 모두 녹인다

- 위의 3과정을 Finish의 값이 True가 될때까지 반복한다

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int row, col, before, result = 0;
bool finish = false;
int arr[100][100];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
struct info {
	int x, y;
};
info tmp;
queue<info> q;

void cal() {
	int t_result = 0;
	for (int i = 0; i < row; i++) 
		for (int j = 0; j < col; j++)
			if (arr[i][j] == 1)
				t_result++;
	if (t_result == 0) finish = true;
	else before = t_result;
}

void spread() {
	int len = q.size();
	for(int k=0;k<len;k++){
		int cx = q.front().x;
		int cy = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx >= 0 && ny >= 0 && nx < col && ny < row && arr[ny][nx]==1) {
				tmp.x = nx;
				tmp.y = ny;
				q.push(tmp);
				arr[ny][nx] = 0;
			}
		}
	}
}

void find_uncheck() {
	bool check[100][100] = { false, };
	queue<info> tq;
	tmp.x = 0;
	tmp.y = 0;
	tq.push(tmp);
	q.push(tmp);
	check[0][0] = true;
	while (!tq.empty()) {
		int cx = tq.front().x;
		int cy = tq.front().y;
		tq.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx >= 0 && ny >= 0 && nx < col && ny < row && !check[ny][nx] && arr[ny][nx] == 0) {
				check[ny][nx] = true;
				tmp.x = nx;
				tmp.y = ny;
				q.push(tmp);
				tq.push(tmp);
			}
		}
	}
}

int main() {
	cin >> row >> col;
	for (int i = 0; i < row; i++) 
		for (int j = 0; j < col; j++) 
			cin >> arr[i][j];		
	
	while (1) {
		result++;
		cal();
		if (finish) {
			result -= 1;
			break;
		}
		find_uncheck();
		spread();
	}
	cout << result << '\n' << before;
	system("pause");
	return 0;
}