C++:: boj 14502 < 연구소 >

주어진 맵에서 임의로 3개의 벽을 세워서 최대한 안전지대를 많이 만들면 되는 문제이다. 최대한 최적화를 해주려 노력했다. dfs와 bfs를 둘다 사용하였다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m, answer, safe_begin = -3;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void spreadViruse(queue<pair<int,int> > virus, vector<vector<int> > board) {// bfs로 바이러스 퍼뜨린다.
	int safe_cnt = safe_begin;
	while (!virus.empty()) {
		pair<int ,int> cur = virus.front(); virus.pop();
		for (int dir=0; dir<4; dir++) {
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx<0 || ny<0 || nx >=n || ny>=m) continue;
			if (board[nx][ny]) continue;
			if (--safe_cnt <= answer) return ;// 안전공간 개수가 이미 구한 답보다 적다면 더 할 필요 X
			board[nx][ny] = 2;
			virus.push({nx, ny});
		}
	}

	answer = safe_cnt;
}

void setWall(int cnt, int x, int y, queue<pair<int,int> >& virus, vector<vector<int> >& board) {
	if (cnt == 3) {// 벽 3개 세웠으면
		spreadViruse(virus, board);
		return ;
	}

	for (int i=x; i<n; i++) {
		int j = i == x ? y : 0;// 벽 3개를 세울때 똑같은 곳에 안세우도록
		for (; j<m; j++) {
			if (!board[i][j]) {
				board[i][j] = 1;
				setWall(cnt+1, x, y+1, virus, board);
				board[i][j] = 0;
			}
		}
	}
}

int main() {
	cin >> n >> m;
	vector<vector<int> > board(n, vector<int>(m));
	queue<pair<int,int> > virus;
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 0) {
				safe_begin++;// 안전한 공간 개수, 나중에 벽세울 것 생각해서 -3
			} else if (board[i][j] == 2) {
				virus.push({i, j});
			}
		}
	}
	setWall(0, 0, 0, virus, board);

	cout << answer <<"\n";
}