[백쥰 2638] 치즈 c++ (완전 탐색)

문제 링크

https://www.acmicpc.net/problem/2638

2638번: 치즈

문제 풀이

외부와 2개의 면이 맞닿아 있는 치즈를 매 턴 제거하는 문제이다.

만약 '외부' 지점을 알 수 있다면, 모든 '외부' 지점을 탐색하며 자신의 상,하,좌,우 에 치즈가 있을 경우, 표시를 하여

2번의 표시가 담긴 치즈 블럭이 존재한다면, 2개의 면이 외부에 노출된 것으로 보고 제거하면 된다. 그렇다면 '외부' 지점을 어떻게 알 수 있을까?

 

이 문제에서 '모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다' 라는 것에 주목하자. (맨 가장 자리 == 테두리이다. )

즉, 테두리는 '무조건 외부' 라는 뜻이다. 따라서 테두리 아무 지점에서나 dfs를 시작하여 상, 하, 좌, 우 로 치즈가 아닌 모든 블록들을 '외부 블록' 으로 써 탐색하고, 만약 '외부 블록'의 상,하,좌,우에 '치즈 블록' 이 존재한다면 count 값을 1 증가시킨다. 이를 통해 매턴 count 값이 2 이상인 치즈들을 제거해나가면 된다. 

 

정답 코드

#include<iostream>
using namespace std;
#include<string.h>
int N, M;
int cnt = 0;
int arr[101][101];
int visit[101][101];
int counts[101][101];
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

//모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것
//-> 테두리에는 치즈 x 
void dfs(int r, int c) {
	visit[r][c] = cnt;
	//cout << r << " " << c << endl;
	for (int d = 0; d < 4; d++) {
		int nr = r + dr[d], nc = c + dc[d];
		if (0 > nr || nr >= N || 0 > nc || nc >= M)continue;
		if (arr[nr][nc] == 1) {
			counts[nr][nc]++;
			continue;
		}
		if (visit[nr][nc]==cnt)continue;
		visit[nr][nc] = cnt;
		dfs(nr, nc);
		
	}


}
//r==3, c==4 일시 counts왜 2?

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> arr[i][j];
		}
	}
	
	while (1) {
		cnt++;
		//if (cnt >= 10)break;
		memset(counts, 0, sizeof(int) * 101 * 101);
		dfs(0, 0); //외부에서 맞닿은 치즈들을 탐색
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (counts[i][j] >= 2)
					arr[i][j] = 0;
			}
		}
		bool noCheese = true;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (arr[i][j] == 1) {
					noCheese = false;
					break;
				}
			}
			if (!noCheese)break;
		}
		if (noCheese) {
			cout << cnt << endl;
			break;
		}
	}
}