백준 [15683] "감시"

문제를 해결하다 3,4번 cctv를 구현하지 못해 답안을 찾아봤다. 처음에 문제 해결을 각 cctv에 해당하는 dx를 만드는 방식으로 구현했는데. 지금까지 해본 경험에서 이렇게 많은 경우의 수를 직접 만들면 무조건 오답인걸 느꼈기 때문에 지금이 오답인걸 알게 되었다. 답은 dx, dy를 하나만 만들고 각 방향을 한번씩 하는 방식으로 구현된걸 알았다.

Backtracking 재귀시 현재 검사한 cctv의 갯수가 전체 cctv의 갯수와 똑같을 경우 map에서 사각지대인 0의 갯수를 확인해 최소 개수인지 확인한다.

90도씩 4번 돌아가기 때문에 4번 반복문을 확인해줫고 tmp[x][y]의 카메라가 몇 번 카메라 인지 확인후 각 카메라에 맞게 감시할 수 있는 구역을 확인한다.

dir에는 현재 cctv의 번호와 90도 회전이 들어가있다. dir의 범위가 0~4로 제한되어야 하기 때문에 %4로 현재 dir을 검사한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

struct CCTV
{
	int x;
	int y;
};

int n, m;

int cctv[8] = { 0 };
int ct = 0;
//cctv 목록
vector<CCTV> v;

int map[9][9];
int result = 999999999;

//1번은 네번 반복
//우 상 좌 하
int dx[4] = { 0,-1,0,1 };
int dy[4] = { 1,0,-1,0 };

void check(int x, int y, int dir) {
	dir %= 4;
	while (1) {
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		x = nx;
		y = ny;
		if (nx < 0 || ny < 0 || nx >= n || ny >= m) return;
		if (map[nx][ny] == 6) return;
		if (map[nx][ny] != 0) continue;
		map[nx][ny] = -1;
	}
}

void backtracking(int cnt) {

	if (cnt == v.size()) {
		int cmp = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 0) {
					cmp++;
				}
			}
		}
		result = min(cmp, result);
		return;
	}

	int x = v[cnt].x;
	int y = v[cnt].y;
	int tmp[9][9];

	for (int dir = 0; dir < 4; dir++) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				tmp[i][j] = map[i][j];

		if (tmp[x][y] == 1) {
			check(x, y, dir);
		}
		else if (tmp[x][y] == 2) {
			check(x, y, dir);
			check(x, y, dir + 2);
		}
		else if (tmp[x][y] == 3) {
			check(x, y, dir);
			check(x, y, dir + 1);
		}
		else if (tmp[x][y] == 4) {
			check(x, y, dir);
			check(x, y, dir + 1);
			check(x, y, dir + 2);
		}
		else if (tmp[x][y] == 5) {
			check(x, y, dir);
			check(x, y, dir + 1);
			check(x, y, dir + 2);
			check(x, y, dir + 3);
		}
		backtracking(cnt + 1);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				map[i][j] = tmp[i][j];
	}

}

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

	cin >> n >> m;

	//입력 받기
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int a;
			cin >> a;
			map[i][j] = a;
			if (a != 6 && a != 0) {
				v.push_back({ i,j});
			}
		}
	}

	backtracking(0);
	
	cout << result;

	return 0;
}