대엉코딩

www.acmicpc.net/problem/2638

1. 풀이방법

- 문제를 보면 bfs를 이용해야 겠다는 생각이 들고,

- 처음에 딱 핵심이다 라고 생각되는 것은 0(빈칸) 중에서 외부공기 / 실내공기 를 나누어 주어야 한다는 것.

- 그리고 문제설정에서 외부공기는 반드시 존재하게끔 되어있습니다.

- 바로 "모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다" 적어도, 4자리는 외부공기라는 것

- 그래서 처음에 이 4점을 기준으로 bfs를 돌려 외부공기를 모두 2로 표시해주고 시작합니다.

- 저 같은 경우 벡터에 치즈의 자리를 모두 넣은 뒤, 이 치즈들이 사라질 때마다 이 자리들을 다시 큐에 넣어

- 이 치즈가 녹음으로써 내부공기 -> 외부공기 가 되는 것들을 체크해주었습니다.

2. 주의사항

- 이런 류의 문제에서 사라지는 c의 위치를 찾았을 때 바로 ground를 2로 바꿔버리면 그 뒤의 치즈들이 이 것에 의해

- 영향을 받을 수 있습니다. 그래서 벡터의서 check를 true로만 바꿔주고, 작업이 끝난뒤에

- check가 true인 것들을 한번에 2로 바꾸어주었습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int n, m;
//1은 치즈 , 0 은 빈칸 , 2는 실외공기
int ground[101][101];
bool visited[101][101];
int cheesecount = 0;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
struct cheese {
	int cx, cy;
	bool check;
};
vector<pair<int, int>> sideindex;
queue<pair<int, int>> tmpq;
vector<cheese> tmpv;

void inputs() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> ground[i][j];
			if (ground[i][j] == 1) {
				cheesecount++; tmpv.push_back({ i,j,false });
			}
		}
	}
	sideindex.push_back({ 0, 0 }); sideindex.push_back({ n - 1,0 });
	sideindex.push_back({ 0,m - 1 }); sideindex.push_back({ n - 1,m - 1 });
}
bool boundcheck(int x, int y) {
	if (x >= 0 && x < n && y >= 0 && y < m) return true;
	else return false;
}
void makeoutside() {
	while (!tmpq.empty()) {
		int qsize = tmpq.size();
		while (qsize--) {
			int nextx = tmpq.front().first;
			int nexty = tmpq.front().second;
			tmpq.pop();
			for (int i = 0; i < 4; i++) {
				int tx = nextx + dx[i]; int ty = nexty + dy[i];
				if (boundcheck(tx, ty) && visited[tx][ty] == false && ground[tx][ty] != 1) {
					visited[tx][ty] = true;
					tmpq.push({ tx,ty });
					ground[tx][ty] = 2;
				}
			}
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	int second = 0;		
	//실외공기 구하기
	for (int i = 0; i < 4; i++) {
		visited[sideindex[i].first][sideindex[i].second] = true;
		ground[sideindex[i].first][sideindex[i].second] = 2;
		tmpq.push(sideindex[i]);
	}
	
	makeoutside();
	while (1) {
		if (cheesecount == 0) break;
		for (int i = 0; i < tmpv.size(); i++) {
			if (tmpv[i].check == true) continue;
			int vsize = 0;
			for (int j = 0; j < 4; j++) { //4방향 탐색
				if (ground[tmpv[i].cx + dx[j]][tmpv[i].cy + dy[j]] == 2) {
					vsize++;
				}
				if (vsize >= 2) {
					cheesecount--;
					visited[tmpv[i].cx + dx[j]][tmpv[i].cy + dy[j]] = true;
					tmpv[i].check = true; //여기는 없어짐
					tmpq.push({ tmpv[i].cx + dx[j],tmpv[i].cy + dy[j] });
					break;
				}
			}
		}
		for (int i = 0; i < tmpv.size(); i++) {
			if (tmpv[i].check == true) {
				ground[tmpv[i].cx][tmpv[i].cy] = 2;
			}
		}
		makeoutside(); //없어진 치즈로 인해 실내공기에서 외부공기가 되는 녀석들 체크
		second++;
	}
	cout << second;
	return 0;
}