백준 15683번 감시 C++

출처 : https://www.acmicpc.net/problem/15683

 

은근히 고려해야 할게 많은 쉽지는 않은 구현 문제이다.

 

각각의 cctv마다 감시할 수 있는 경우의 수가 다르다. 예를 들면, 1번 cctv는 상, 하, 좌, 우 4가지 경우를 감시할 수 있고, 

2번 cctv는 상하, 좌우 2가지 경우를 감시할 수 있다. 이 경우들을 비트로 만들어서 저장하였다. 위, 오른쪽, 아래, 왼쪽 순서로 저장했고 감시할 수 있으면 1, 못하면 0으로 저장했다. 

2번 cctv의 경우는 상하, 좌우 2가지 경우가 있기 때문에 1010, 0101 두 개를 저장했다.

 

다음은 백트래킹을 이용하여 모든 경우를 탐색했는데, 중간에 마스크를 이용해서 감시할 수 있는 지역을 알아냈다.

마스크는 1000부터 시작하여 오른쪽으로 한 칸씩 옮겨가는데, 각 경우마다 cctv와 &연산을 해서 0이 아니라면 맵 끝이나 벽을 만날 때까지 감시하는 영역을 넓혀주었다.

 

예를 들어 2번 cctv의 1010을 탐색한다고 하면, 

마스크가 1000일때는 1010 & 1000 = 1000 이므로 0이 아니기 때문에 위로 쭉 영역을 넓히고, 

마스크가 0100일때는 1010 & 0100 = 0000 이므로 넘어가고

마스크가 0010일때는 1010 & 0010 = 0010 이므로 아래로 쭉 영역을 넓히고,

마스크가 0001일때는 1010 & 0001 = 0000 이므로 넘어간다.

결과적으로 1010이 나타내는 상하로 감시하는 영역을 넓힐 수 있다.

 

이런 방식과 백트래킹을 이용하여 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;


int n, m;
int ans = 987654321;
vector<vector<int>> board(8, vector<int>(8));
vector<vector<int>> cctv(6, vector<int>());
vector<pair<int, pair<int, int>>> locate;

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

void BT(int num) {
	if (num >= locate.size()) {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (board[i][j] == 0) cnt++;
			}
		}
		ans = min(ans, cnt);
		return;
	}
	vector<vector<int>> tmpBoard(8, vector<int>(8));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			tmpBoard[i][j] = board[i][j];
		}
	}
	for (auto a : cctv[locate[num].first]) {
		int mask = 0b1000;
		for (int i = 0; i < 4; i++) {
			if (a & mask) {
				int row = locate[num].second.first;
				int col = locate[num].second.second;
				while (true) {
					int nextRow = row + dRow[i];
					int nextCol = col + dCol[i];
					if (nextRow < 0 || nextRow >= n) break;
					if (nextCol < 0 || nextCol >= m) break;
					if (board[nextRow][nextCol] == 6) break;
					if (board[nextRow][nextCol] == 0) {
						board[nextRow][nextCol] = 7;
					}
					row = nextRow;
					col = nextCol;
				}
			}
			mask = mask >> 1;
		}
		BT(num + 1);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				board[i][j] = tmpBoard[i][j];
			}
		}
	}
}

void Init() {
	cctv[1].push_back(0b1000);
	cctv[1].push_back(0b0100);
	cctv[1].push_back(0b0010);
	cctv[1].push_back(0b0001);

	cctv[2].push_back(0b0101);
	cctv[2].push_back(0b1010);

	cctv[3].push_back(0b1100);
	cctv[3].push_back(0b0110);
	cctv[3].push_back(0b0011);
	cctv[3].push_back(0b1001);

	cctv[4].push_back(0b1101);
	cctv[4].push_back(0b1110);
	cctv[4].push_back(0b0111);
	cctv[4].push_back(0b1011);

	cctv[5].push_back(0b1111);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			if (board[i][j] >= 1 && board[i][j] <= 5) {
				locate.push_back({ board[i][j],{ i,j } });
			}
		}
	}
}

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

	Init();
	BT(0);
	cout << ans;
};