[C++]백준 2638번: 치즈

문제 출처

BFS/DFS보단 "구현"문제가 맞는 것 같다.

이 문제에서 유의해야할 사항은 다음과 같다.

1. 빈 공간은 외부의 빈 공간(-1)/ 치즈 속의 빈공간(0) 두개로 분리된다.
2. 두 면의 외부의 빈공간에 노출된 치즈를 한 꺼번에 업데이트 해야한다.
3. 치즈가 녹음으로써 치즈 속의 빈공간이 외부의 빈공간에 노출될 수 있다.
4. 가장자리는 무조건 빈 공간(외부의 빈 공간)이므로 시작하자마자 (0,0)으로부터 외부의 빈 공간을 찾아 마킹을 한다. 나는 -1로 하였다.

그리고 빈 공간을 찾거나 치즈 속의 빈 공간을 외부의 빈 공간으로 채울 때 DFS든 BFS든 아무거나 사용해도 좋다. 요즘 BFS를 안썼기 때문에 BFS로 구현하였다.
다음은 코드 전문이다. 좀 길다.

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int x[] = { -1,0,1,0 };
int y[] = { 0,-1,0,1 };

typedef pair<int, int> ii;

void BFS(vector<vector<int>> &place, int yy, int xx, vector<vector<bool>> check, int &N, int &M) {
	queue<ii> que;
	que.push(ii(yy, xx));
	while ( !que.empty() ) {
		int i = que.front().first;
		int j = que.front().second;
		que.pop();
		if ( check[i][j] )continue;
		check[i][j] = 1;
		place[i][j] = -1;	//외부
		for ( int k = 0; k < 4; k++ ) {
			int xtmp = x[k];
			int ytmp = y[k];
			if ( i + ytmp < 0 || i + ytmp >= N || j + xtmp < 0 || j + xtmp >= M || place[i + ytmp][j + xtmp] != 0 )continue;
			que.push(ii(i + ytmp, j + xtmp));
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;
	vector<vector<int>> place(N, vector<int>(M));
	vector<ii> cheeze;
	vector<vector<bool>> check(N, vector<bool>(M, 0));
	for ( int i = 0; i < N; i++ ) {
		for ( int j = 0; j < M; j++ ) {
			cin >> place[i][j];
			if ( place[i][j] == 1 )cheeze.emplace_back(ii(i, j));
		}
	}
	queue<ii> que;
	que.push(ii(0, 0));
	while ( !que.empty() ) {
		int i = que.front().first;
		int j = que.front().second;
		que.pop();
		if ( check[i][j] )continue;
		check[i][j] = 1;
		place[i][j] = -1;	//외부
		for ( int k = 0; k < 4; k++ ) {
			int xtmp = x[k];
			int ytmp = y[k];
			if ( i + ytmp < 0 || i + ytmp >= N || j + xtmp < 0 || j + xtmp >= M ||place[i+ytmp][j+xtmp] != 0 )continue;
			que.push(ii(i + ytmp, j + xtmp));
		}
	}
	int day = 0;
	fill(check.begin(), check.end(), vector<bool>(M, 0));
	while ( 1 ) {
		if ( cheeze.size() == 0 )break;
		int count = 0;
		vector<ii> list;
		for ( int i = 0; i < cheeze.size();) {
			int yy = cheeze[i].first;
			int xx = cheeze[i].second;
			if ( place[yy + 1][xx] == -1 )count++;
			if ( place[yy - 1][xx] == -1 )count++;
			if ( place[yy][xx + 1] == -1 )count++;
			if ( place[yy][xx - 1] == -1 )count++;
			if ( count >= 2 ) {
				list.emplace_back(ii(yy, xx));
				cheeze.erase(cheeze.begin() + i);
			}
			else {
				i++;
			}
			count = 0;

		}
		for ( int i = 0; i < list.size(); i++ ) {
			int yy = list[i].first;
			int xx = list[i].second;
			place[yy][xx] = -1;
			if ( place[yy + 1][xx] == 0 ) {
				BFS(place, yy + 1, xx, check, N, M);
			}
			if ( place[yy - 1][xx] == 0 ) {
				BFS(place, yy - 1, xx, check, N, M);

			}
			if ( place[yy][xx + 1] == 0 ) {
				BFS(place, yy, xx + 1, check, N, M);

			}
			if ( place[yy][xx - 1] == 0 ) {
				BFS(place, yy, xx - 1, check, N, M);
			}
		}
		day++;
	}

	cout << day << endl;
	return 0;
}

for ( int i = 0; i < N; i++ ) {
		for ( int j = 0; j < M; j++ ) {
			cin >> place[i][j];
			if ( place[i][j] == 1 )cheeze.emplace_back(ii(i, j));
		}
	}

여기서 치즈의 좌표를 치즈벡터에 넣었다.

queue<ii> que;
	que.push(ii(0, 0));
	while ( !que.empty() ) {
		int i = que.front().first;
		int j = que.front().second;
		que.pop();
		if ( check[i][j] )continue;
		check[i][j] = 1;
		place[i][j] = -1;	//외부
		for ( int k = 0; k < 4; k++ ) {
			int xtmp = x[k];
			int ytmp = y[k];
			if ( i + ytmp < 0 || i + ytmp >= N || j + xtmp < 0 || j + xtmp >= M ||place[i+ytmp][j+xtmp] != 0 )continue;
			que.push(ii(i + ytmp, j + xtmp));
		}
	}

이 부분이 시작하자마자 외부의 빈 공간을 찾는 과정이다. BFS로 진행하였고 외부의 빈 공간을 -1로 place에 마킹하였다.

for ( int i = 0; i < cheeze.size();) {
			int yy = cheeze[i].first;
			int xx = cheeze[i].second;
			if ( place[yy + 1][xx] == -1 )count++;
			if ( place[yy - 1][xx] == -1 )count++;
			if ( place[yy][xx + 1] == -1 )count++;
			if ( place[yy][xx - 1] == -1 )count++;
			if ( count >= 2 ) {
				list.emplace_back(ii(yy, xx));
				cheeze.erase(cheeze.begin() + i);
			}
			else {
				i++;
			}
			count = 0;

		}

치즈벡터를 돌면서 2면이 외부의 빈 공간인 치즈를 찾아 치즈벡터에선 없애고 list벡터에 넣었다. 이 list벡터는 치즈가 없어짐으로써 생기는 외부의 빈 공간과 치즈 내부의 빈 공간을 찾아내기 위해 사용되는 벡터이다. 밑에서 설명하겠다.

for ( int i = 0; i < list.size(); i++ ) {
			int yy = list[i].first;
			int xx = list[i].second;
			place[yy][xx] = -1;
			if ( place[yy + 1][xx] == 0 ) {
				BFS(place, yy + 1, xx, check, N, M);
			}
			if ( place[yy - 1][xx] == 0 ) {
				BFS(place, yy - 1, xx, check, N, M);

			}
			if ( place[yy][xx + 1] == 0 ) {
				BFS(place, yy, xx + 1, check, N, M);

			}
			if ( place[yy][xx - 1] == 0 ) {
				BFS(place, yy, xx - 1, check, N, M);
			}
		}

list에 있는 삭제될 치즈의 좌표를 돌면서 해당 치즈를 -1로 마킹해 삭제하고 그 주변에 0. 즉 치즈내부의 빈 공간을 확인하여 빈 공간이 있으면 BFS로 -1로 채우는 과정을 반복한다.

BFS함수는 위에 정의해 두었다.