백준 15683번 감시 (골드 3) 백트래킹, 시뮬레이션

백크래킹과 시뮬레이션 알고리즘을 사용하는 문제입니다.

 

풀이

1. cctv위치 및 번호 방향을 정하는 구조체를 만든다

2. cctv의 갯수만큼의 for문 안에 모든 각도를 탐색하는 for문을 0~3까지 이중포문을 만든다.

3. func로 백트래킹을 돌리면서 check함수로 해당 방향으로 뻗어나가면서 체크해준다

4. 체크가 몇개 되어있는지 세어준다음 board를 다시 0으로 초기화 시킨다

5. 체크의 최대값을 max함수로 구한다.

6. n *m  - (6의 갯수 + 최대 체크 개수 + cctv갯수) 모든 크기에서 사각지대가 아닌것을 뺀다

#include <iostream> 
#include <queue>
#include <vector>
#include <algorithm>


using namespace std;


int mins = 100000000;
int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { -1, 0, 1, 0};

int arr[8][8] = { 0, };
int visit[8][8] = { 0, };
int num[100] = { 0, };

int n, m;

struct member {
	int x;
	int y;
	int val;
};

vector<member>  v;




void clear() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visit[i][j] = 0;
		}
	}
}


void counts() {
	int count = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visit[i][j] == 0 && arr[i][j] != 6) {
				count++;
			}
		}
	}

	mins = min(mins, count);
}


void check(int direction, member ms) {

	direction = direction % 4;

	int nx = ms.x;
	int ny = ms.y;

	while (arr[nx][ny] != 6
		&& nx >= 0 && nx < n
		&& ny >= 0 && ny < m
		) {
		
		visit[nx][ny] = 1;

		nx += dx[direction];
		ny += dy[direction];
	}
	return;
}


void func(int t) {

	if (t == v.size()) {
		clear();

		for (int i = 0; i < v.size(); i++) {
			member ms = v[i];
			int rotate = num[i];

			switch (ms.val) {
				case 1:
					check(rotate, ms);
					break;
				case 2:
					check(rotate, ms);
					check(rotate+2, ms);
					break;
				case 3:
					check(rotate, ms);
					check(rotate+1, ms);
					break;
				case 4:
					check(rotate, ms);
					check(rotate+1, ms);
					check(rotate + 2, ms);
					break;
				case 5: 
					check(rotate, ms);
					check(rotate + 1, ms);
					check(rotate + 2, ms);
					check(rotate + 3, ms);
					break;
	
			}
		}

		counts();
	
	}
	else {
		
		for (int i = 0; i < 4; i++) {
			num[t] = i;
			func(t + 1);
		}
	}
	return;
}

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++) {
			cin >> arr[i][j];

			if (arr[i][j] != 6 && arr[i][j] != 0) {
				v.push_back({
					i,
					j,
					arr[i][j]
				});
			}
		}
	}


	func(0);

	cout << mins;

}