15683 감시

문제링크

코드 설명

CCTV의 종류를 입력받은후 각각의 가지수를 전부 카운트 해보는 문제이다. 문제에 들어가기전 완전탐색이 맞는지 시간초과가 안날지 최악의case를 먼저 계산해보는 습관을 가지자

4^8 * 64 이므로 대략 400만정도이므로 1초 안에 가능하다.

그다음에는 각 CCTV마다 탐색할수있는 방향의 개수를 담은 배열을 만들자(편함!)
rotate_arr[]={4,2,4,4,1};
이건 완전탐색에서 type별 branch 개수가 된다

find()함수를 만들어서 한 방향을 매개변수로 받고 그 방향에서 벽을 만나기전까지 전부 탐색한다(#)
방향만큼 함수를 호출한다(코드주석참고)

코드

#include<iostream>
#include<vector>
using namespace std;
struct CCTV {
	int type; //0,1,2,3
	int y;
	int x;
};
CCTV cctv[8];
int map[8][8];
int answer = 1000;
int N, M;
int K; //CCTV 개수
int rotate_arr[] = { 4,2,4,4,1 }; //type별 총 회전가능 횟수

void find(int dir, CCTV cctv) { // 한방향 모두 탐색하는 함수
	dir = dir % 4;

	if (dir == 0) {//동쪽 끝까지
		for (int i = cctv.x + 1; i < M; i++) {
			if (map[cctv.y][i] == 6) break;
			map[cctv.y][i] = -1; //-1로 탐색 완료 표시 (#)
		}
	}
	if (dir == 1) { //북쪽
		for (int i = cctv.y - 1; i >= 0; i--) {
			if (map[i][cctv.x] == 6) break;
			map[i][cctv.x] = -1; 
		}
	}
	if (dir == 2) { //서쪽
		for (int i = cctv.x - 1; i >= 0; i--) {
			if (map[cctv.y][i] == 6) break;
			map[cctv.y][i] = -1;
		}
	}
	if (dir == 3) { //남쪽
		for (int i = cctv.y + 1; i < N; i++) {
			if (map[i][cctv.x] == 6) break;
			map[i][cctv.x] = -1;
		}
		
	}


}


void dfs(int level) {
	if (level == K) {
		int cnt = 0;//사각지대크기 count
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if (map[y][x] == 0) cnt++;
			}
		}
		answer = min(answer, cnt);
		return;
	}
	int backup[8][8];
	int type = cctv[level].type;
	for (int i = 0; i < rotate_arr[type]; i++) { //각 cctv type별로 탐색
		memcpy(backup, map, sizeof(map)); //map을 backup복사
		if (type == 0) { //한방향만 탐색
			find(i, cctv[level]);
		
		}
		else if (type == 1) {//두방향탐색
			find(i, cctv[level]);
			find(i+2, cctv[level]);
		}
		else if (type == 2) { //두방향
			find(i, cctv[level]);
			find(i+1, cctv[level]);
			
		}
		else if (type == 3) { //세방향
			find(i, cctv[level]);
			find(i + 1, cctv[level]);
			find(i + 2, cctv[level]);
		}
		else if (type == 4) { //네방향
			find(i, cctv[level]);
			find(i + 1, cctv[level]);
			find(i + 2, cctv[level]);
			find(i + 3, cctv[level]);
		}
		dfs(level + 1);
		memcpy(map, backup, sizeof(backup)); //탐색완료후 backup-> map복사 (완전탐색을 위해 한단계 탐색이후 돌아올때 그전 map상태 저장)
	}
}
int main() {
	cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];
			if (map[y][x] != 0 && map[y][x] != 6) {
				cctv[K].y = y;
				cctv[K].x = x;
				cctv[K].type = map[y][x] - 1;
				K++;
			}
		}
	}
	dfs(0);
	cout << answer;
	return 0;
}