[BOJ] #15683 _ 감시

[감시] https://www.acmicpc.net/problem/15683

15683번: 감시

dfs를 이용하여 각 cctv가 볼 수 있는 4가지 방향의 모든 경우의 수를 고려해주었다.

모든 cctv의 방향이 결정되면, 각 cctv에 맞게 감시하고 사각지대의 수를 구해 최소 값을 갱신하였다.

(cctv의 좌표는 cctv배열에 저장해주었다.)

 

[ 소스 코드 ]

#include <cstdio>
#include <algorithm>
#define MAX 8

using namespace std;

int dx[] = { 0,1,0,-1 }, dy[] = { -1,0,1,0 };
int N, M;
int office[MAX][MAX], chk[MAX][MAX], cctv_d[MAX];
int minVal = 99999999, cctv_num;
pair<int, int> cctv[MAX];

void solve(int idx, int d);
int count_space();
void copy_arr();
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &office[i][j]);
			if (office[i][j] > 0 && office[i][j] < 6) cctv[cctv_num++] = make_pair(i, j);
		}
	}

	for(int i=0; i<4; i++) solve(0, i);

	printf("%d\n", minVal);

	return 0;
}

void solve(int idx, int d) {
	cctv_d[idx] = d;
	if (idx + 1 >= cctv_num) {
		minVal = min(minVal, count_space());
		return;
	}

	for (int i = 0; i < 4; i++) solve(idx + 1, i);
}

int count_space() {
	int count = 0, tmp_x, tmp_y;

	copy_arr();
	for (int idx = 0; idx < cctv_num; idx++) {
		tmp_x = cctv[idx].second;
		tmp_y = cctv[idx].first;
		while (1) {
			tmp_x += dx[cctv_d[idx]];
			tmp_y += dy[cctv_d[idx]];
			if (tmp_x < 0 || tmp_y < 0 || tmp_x >= M || tmp_y >= N) break;
			if (office[tmp_y][tmp_x] == 6) break;
			chk[tmp_y][tmp_x] = 1;
		}
		if (office[cctv[idx].first][cctv[idx].second] == 2) {
			tmp_x = cctv[idx].second;
			tmp_y = cctv[idx].first;
			while (1) {
				tmp_x -= dx[cctv_d[idx]];
				tmp_y -= dy[cctv_d[idx]];
				if (tmp_x < 0 || tmp_y < 0 || tmp_x >= M || tmp_y >= N) break;
				if (office[tmp_y][tmp_x] == 6) break;
				chk[tmp_y][tmp_x] = 1;
			}
		}
		else {
			for (int i = 1; i < office[cctv[idx].first][cctv[idx].second] - 1; i++) {
				tmp_x = cctv[idx].second;
				tmp_y = cctv[idx].first;
				cctv_d[idx]++;
				if (cctv_d[idx] >= 4) cctv_d[idx] = 0;
				while (1) {
					tmp_x += dx[cctv_d[idx]];
					tmp_y += dy[cctv_d[idx]];
					if (tmp_x < 0 || tmp_y < 0 || tmp_x >= M || tmp_y >= N) break;
					if (office[tmp_y][tmp_x] == 6) break;
					chk[tmp_y][tmp_x] = 1;
				}
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (chk[i][j] == 0) count++;
		}
	}

	return count;
}

void copy_arr() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) chk[i][j] = office[i][j];
	}
}