백준 2636 C++

치즈 문제 바로가기

해당문제는 저는 DFS를 사용해서 풀었습니다.
다만, 어차피 DFS를 한번만 0,0에서 시작하므로 BFS와 다를것이 없습니다.

판의 0,0은 무조건 공기입니다. 그러므로, dfs(0,0)으로 시작합니다.

void dfs(int i, int j) {
	visited[i][j] = true;
	for (int a = 0; a < 4; a++) {
		int nx = i + dx[a];
		int ny = j + dy[a];
		if (nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny]) {
			if (map[nx][ny] == 0) {
				dfs(nx, ny);
			}
			else {
				visited[nx][ny] = true;
				map[nx][ny] = 0;
				cheese++;
			}
		}
	}

}

핵심은 이것입니다.
i,j가 0,0이라고 가정하고 상하좌우를 살펴봅니다.
그리고 만약 내가 공기의 좌표인데 만약 다음 좌표가 0으로 공기이다.
그러면 dfs로 재귀호출을해서 다음 공기좌표의 상하좌우를 살펴봅니다.

그러나, 만약 내가 공기인데 다음좌표가 치즈이면, 0으로 갱신하고 cheese를 ++합니다.
중요한것은 방문처리를 치즈도 해줘야한다는 것입니다.
000
011
011
만약 지금 1,0좌표의 공기 0에 있다고 가정하겠습니다. 만약 visited처리를 하지 않고 map만 바꾼다면
000
001
011
이 될것입니다.
그리고
1,0 -> 0,0 -> 0,1 좌표에와서
0,1에서 상하좌우를 살펴봅니다. 앞서서 visited처리를 해주지 않았으므로 0이니까 1,1을 재귀함수로 부르게 됩니다. 그러면 1,1에서 상하좌우를 살펴보게되면 2,2가 1이므로 삭제하게 됩니다.

고로 치즈를 지우면 visited처리를 해줘야합니다.

#include <iostream>
#include <vector>
#include <utility>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;

int N;
int M;

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,1,-1 };

int map[101][101];
bool visited[101][101];

int cheese = 0;

void dfs(int i, int j) {
	visited[i][j] = true;
	for (int a = 0; a < 4; a++) {
		int nx = i + dx[a];
		int ny = j + dy[a];
		if (nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny]) {
			if (map[nx][ny] == 0) {
				dfs(nx, ny);
			}
			else {
				visited[nx][ny] = true;
				map[nx][ny] = 0;
				cheese++;
			}
		}
	}

}

bool check(int map[101][101]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j]) return false;
		}
	}
	return true;
}

void solution(int cnt) {
	cheese = 0;
	//이걸로 공기부분 true로 놓기
	dfs(0, 0);

	int temp = 0;

//map에 치즈가 있는지 검사
	bool flag = true;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j]) { flag = false; break; }
		}
		if (!flag) break;
	}
    //치즈가 없다면 정답
	if (flag) {
		cout << cnt + 1 << "\n";
		cout << cheese;
		return;
	}
    //치즈가 없다면 다시 검사
	memset(visited, false, sizeof(visited));
	solution(cnt + 1);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	cin >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int tmp = 0;
			cin >> tmp;
			map[i][j] = tmp;
		}
	}

	solution(0);
}