C++:: boj 15683 < 감시 >

난이도에 비해 좀 까다로운 문제이다. 핵심은 카메라마다 회전이 가능하다는 점과, 대칭으로 감시하는 카메라의 경우 예외 처리를 해주면 최적화가 가능하다는 점이다.

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

int n, m, answer = INT32_MAX;

/*
 0
3 1
 2
*/

vector<vector<int>> cctv = {{0}, {0,2}, {0, 1}, {0, 1, 2}, {0, 1, 2, 3}};// 카메라가 보는 형태
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int getSafeArea(vector<vector<int> >& board) {// 개수 세기
	int res = 0;
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			if (!board[i][j]) res++;
		}
	}
	return res;
}

bool checkArea(int x, int y) {// 범위 내인지
	if (x < 0 || y < 0 || x >= n || y >= m) return false;
	return true;
}

vector<vector<int> > activateCCTV(int x, int y, vector<int> dirs, vector<vector<int> > board) {
	for (auto& dir : dirs) {// 주어진 방향으로 전부 체크해준다.
    // 이때 cctv인 부분을 지날때는 체크 안해주고 지나간다.
		int nx = x + dx[dir], ny = y + dy[dir];
		while (checkArea(nx, ny) && (board[nx][ny] != 6)) {
			if (!board[nx][ny]) board[nx][ny] = 7;
			nx += dx[dir];
			ny += dy[dir];
		}
	}
	return board;
}

void dfs(vector<vector<int> > board, queue<pair<int,int>> cctv_pos) {
	if (cctv_pos.empty()) {// 모든 카메라 방향 설정하면
		answer = min(answer, getSafeArea(board));
		return ;
	}
	pair<int, int> cur = cctv_pos.front();
	cctv_pos.pop();
	int cctv_num = board[cur.first][cur.second];
	vector<int> dirs = cctv[cctv_num-1];// 현재 카메라가 볼 수 있는 방향들
	for (int i=0; i<4; i++) {
		if (cctv_num == 2 && i >= 2) continue;// 대칭
		if (cctv_num == 5 && i >= 1) continue;// 예외
		for (auto& dir : dirs) {// 90도 회전
			dir = (dir + 1) % 4;
		}
		dfs(activateCCTV(cur.first, cur.second, dirs, board), cctv_pos);
	}
}

int main() {
	cin >> n >> m;
	vector<vector<int> > board(n, vector<int>(m));
	queue<pair<int,int>> cctv;
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			cin >> board[i][j];
			if (board[i][j] && board[i][j] != 6) {
				cctv.push({i, j});
			}
		}
	}
	dfs(board, cctv);
	cout << answer << "\n";
}