[Algorithm][C++] BOJ 15683 감시

url: https://hotamul.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts 

TISTORY

 

풀이 핵심

1. https://na982.tistory.com/95 참고

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int R, C, ret;
int map[8][8];
struct CCTV { int type, r, c; };
CCTV cctv[8];
int cctv_size;
const int rot_size[] = { 4,2,4,4,1 };

void update(int dir, CCTV cctv) {
	dir %= 4;
	if (dir == 0) {
		for (int c = cctv.c + 1; c < C; c++) {
			if (map[cctv.r][c] == 6) break;
			map[cctv.r][c] = -1;
		}
	}
	if (dir == 1) {
		for (int r = cctv.r - 1; r >= 0; r--) {
			if (map[r][cctv.c] == 6) break;
			map[r][cctv.c] = -1;
		}
	}
	if (dir == 2) {
		for (int c = cctv.c - 1; c >= 0; c--) {
			if (map[cctv.r][c] == 6) break;
			map[cctv.r][c] = -1;
		}
	}
	if (dir == 3) {
		for (int r = cctv.r + 1; r < R; r++) {
			if (map[r][cctv.c] == 6) break;
			map[r][cctv.c] = -1;
		}
	}
}

void cpy_map(int a[8][8], int b[8][8]) {
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			a[r][c] = b[r][c];
		}
	}
}

void dfs(int idx) {
	if (idx == cctv_size) {
		int tmp = 0;
		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (map[r][c] == 0) tmp++;
			}
		}
		if (tmp < ret) ret = tmp;
		return;
	}

	int backup[8][8];
	int type = cctv[idx].type;
	cpy_map(backup, map);
	for (int dir = 0; dir < rot_size[type]; dir++) {
		if (type == 0) {
			update(dir, cctv[idx]);
		}
		if (type == 1) {
			update(dir, cctv[idx]);
			update(dir + 2, cctv[idx]);
		}
		if (type == 2) {
			update(dir, cctv[idx]);
			update(dir + 1, cctv[idx]);
		}
		if (type == 3) {
			update(dir, cctv[idx]);
			update(dir + 1, cctv[idx]);
			update(dir + 2, cctv[idx]);
		}
		if (type == 4) {
			update(dir, cctv[idx]);
			update(dir + 1, cctv[idx]);
			update(dir + 2, cctv[idx]);
			update(dir + 3, cctv[idx]);
		}
		dfs(idx + 1);
		cpy_map(map, backup);
	}
}

int main() {
	scanf("%d %d", &R, &C);
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			scanf("%d", &map[r][c]);
			if (map[r][c] != 0 && map[r][c] != 6) {
				cctv[cctv_size].r = r;
				cctv[cctv_size].c = c;
				cctv[cctv_size++].type = map[r][c] - 1;
			}
		}
	}
	ret = 100;
	dfs(0);
	printf("%d", ret);
	return 0;
}