[백준 2638 C++] 치즈

치즈 문제 링크 (백준(BOJ) 2638번 문제): https://www.acmicpc.net/problem/2638

2638번: 치즈

문제 풀이 

백준 2638번 치즈 문제는 흔히 BFS (Breadth First Search) 알고리즘을 사용하는 문제이다. 이 문제에서 주목할 점은 치즈의 내부와 외부를 구분하는 것이 핵심이었다. 그리하여, 쓴이는 MAP을 돌면서 0인 부분에서 BFS를 시행하여 각각의 (치즈가 없는)공간을 번호로 나눠주었고 여러 공간들 중에 BFS 수행 시 범위를 벗어나는 값이 있다면 벡터에 저장해준 후 나중에 비교해주었다. 

위 예제를 보면, 치즈 조각이 없는 공간이 총 3개로 구분될 수 있는데, 이것 영역들 중에서 BFS 수행 시 ( y < 0 || y >= R || x < 0 || x >= C) 범위에 접근하는 영역은 치즈의 외부 영역이라고 인식하였다. 

 

그리하여, 이를 코드로 나타내면 아래와 같이 나타낼 수 있다. 

	#include <iostream>
	#include <queue>
	#include <cstring>
	#define MAX 101
	using namespace std;
	int MAP[MAX][MAX];
	int value[MAX][MAX];
	int dx[4] = {-1, 0, 1, 0} ;
	int dy[4] = { 0, 1, 0,-1} ;
	int R, C ;
	int result ;
	vector<int> outside_v ;
	void Outside() {
	int p = 0 ;
	memset(value, 0, sizeof(value)) ;
	for (int i = 0 ; i < R; i++) {
	for (int j = 0 ; j < C; j++) {
	if ( MAP[i][j] == 0 && value[i][j] == 0) {
	bool out = false;
	p--;
	queue<pair<int,int> > Q;
	Q.push(make_pair(j, i)) ;
	value[i][j] = p ;
	while(!Q.empty()) {
	int curr_x = Q.front().first ;
	int curr_y = Q.front().second ;
	Q.pop() ;
	for (int k = 0 ; k < 4 ; k++) {
	int dir_x = curr_x + dx[k] ;
	int dir_y = curr_y + dy[k] ;
	if (dir_x < 0 || dir_x >= C || dir_y < 0 || dir_y >= R) {
	out = true;
	continue ;
	}
	if (MAP[dir_y][dir_x] != 0 || value[dir_y][dir_x] != 0) continue ;
	value[dir_y][dir_x] = p ;
	Q.push(make_pair(dir_x, dir_y)) ;
	}
	}
	// 바깥 영역의 경우 저장
	if ( out ) {
	outside_v.push_back(p) ;
	}
	} else if ( MAP[i][j] == 1 ) {
	value[i][j] = 1;
	}
	}
	}
	}
	void Remove() {
	for (int i = 0 ; i < R ; i++ ) {
	for (int j = 0 ; j < C ; j++) {
	if ( MAP[i][j] == 1 ) {
	int c = 0 ;
	int dirV[4] = {0, } ;
	for (int k = 0 ; k < 4; k++) {
	int dir_x = j + dx[k] ;
	int dir_y = i + dy[k] ;
	if ( dir_x < 0 || dir_x >= C || dir_y < 0 || dir_y >= R) continue ;
	if ( value[dir_y][dir_x] < 0 ) {
	dirV[k] = value[dir_y][dir_x] ;
	// 인접한 칸들 중 2개가 외부 영역인 경우
	for (int ch = 0 ; ch < k ; ch++) {
	if ( dirV[ch] != 0 && dirV[ch] == value[dir_y][dir_x] ) {
	bool check = false ;
	for (int p = 0 ; p < outside_v.size(); p++) {
	if ( outside_v[p] == dirV[ch] ) {
	check = true;
	break ;
	}
	}
	if ( check ) {
	MAP[i][j] = 0 ;
	break;
	}
	}
	}
	}
	}
	}
	}
	}
	}
	bool Finish() {
	int v = value[0][0];
	for (int i = 0 ; i < R; i++ ) {
	for (int j = 0; j < C; j++) {
	if ( v != value[i][j]) {
	return false;
	}
	}
	}
	return true;
	}
	void Input() {
	cin >> R >> C;
	for (int i = 0 ; i < R; i++) {
	for (int j = 0 ; j < C; j++) {
	cin >> MAP[i][j] ;
	}
	}
	}
	int main(void) {
	ios::sync_with_stdio(false) ;
	cin.tie(0);
	Input() ;
	while (1) {
	Outside();
	if ( Finish() ) break;
	Remove() ;
	result++;
	outside_v.clear();
	}
	cout << result << '\n';
	return 0 ;
	}

view raw 2638.cpp hosted with ❤ by GitHub