[C++]백준14502번 연구소

문제는 다음과 같다.

오늘은 백준14502번 연구소 문제를 풀어보도록 하자. dfs로 벽을 세워야 한다. 벽은 항상 3개를 세워야하므로 dfs의 백트래킹 조건은 벽세운 갯수 == 3일 때다. 그 후 바이러스가 퍼진다. 최댓값 갱신 후 return을 하면 된다.

최댓값을 갱신한 후엔 모든 맵의 visit처리를 해제해주어야 한다. 왜냐하면 다음 벽을 3개를 세우면 또 다시 바이러스를 퍼뜨려야하므로 그렇다.

                                     [코드]
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct pos {
	int y;
	int x;
};
vector<pos>two_location;
int map[8][8];
bool visit[8][8];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int R, C, answer = -100, init_value;

void safe_area(int temp) {
	queue<pos>Q;
	for (int i = 0; i < two_location.size(); i++) {
		Q.push({ two_location[i].y,two_location[i].x });
	}

	while (!Q.empty()) {
		int y = Q.front().y;
		int x = Q.front().x;

		Q.pop();

		for (int i = 0; i < 4; i++) {
			int my = y + dir[i][0];
			int mx = x + dir[i][1];

			if (my >= 0 && mx >= 0 && my < R && mx < C) {
				if (map[my][mx] == 0 && !visit[my][mx]) {
					Q.push({ my,mx });
					visit[my][mx] = true;
					temp--;
				}
			}
		}
	}
	if (answer < temp) {
		answer = temp;
	}
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			visit[i][j] = false;
		}
	}
}

void make_wall(int y, int x, int cnt) {
	if (cnt == 3) {
		int temp = init_value - 3;
		safe_area(temp);
		return;
	}
	for (int i = y; i < R; i++) {
		for (int j = x; j < C; j++) {
			if (map[i][j] == 0) {
				map[i][j] = 1;
				make_wall(i,j+1,cnt+1);
				map[i][j] = 0;
			}
		}
		x = 0;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> R >> C;
	init_value = R * C;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				two_location.push_back({ i,j });
			}if (map[i][j] == 1 || map[i][j] == 2) {
				init_value--;
			}
		}
	}
	make_wall(0,0,0);
	cout << answer;
}