[BOJ] 15683 감시 (C++)

https://www.acmicpc.net/problem/15683

15683번: 감시

케이스별 회전의 경우가 다를 경우

이와 같은 탐색 문제는 카메라별 회전 가능 케이스를 저장해놓고 회전시키는 것이 좋다.

const int rot_size[] = {4, 2, 4, 4, 1}

const int rot_size[] = {4, 2, 4, 4, 1};

void DFS(int cctv_index) {

	if(cctv_index == cctv_size) {
		// ...
		return;
	}

	int type = cctv[cctv_index].no;
	for(int dir=0; dir<rot_size[type]; dir++) {
    	//...
		// 동남서북
		if(type == 0) {
			update(dir, cctv[cctv_index]);
		}
		// ...
		DFS(cctv_index+1);
        // ...

	}
}

방향별 탐색

void update(int dir, CCTV cctv) {

	dir = (dir % 4);
	// 동남서북
	if(dir == 0) {
		for(int x=cctv.x+1; x<m; x++) {
			if(map[cctv.y][x] == 6) // 벽을 마주했을 경우
				break;
			else 
				map[cctv.y][x] = -1; // 탐색했다는 표시
		}
	}
	if(dir == 1) {
		for(int y=cctv.y+1; y<n; y++) {
			if(map[y][cctv.x] == 6)
				break;
			else 
				map[y][cctv.x] = -1;
		}
		
	}
	if(dir == 2) {
		for(int x=cctv.x-1; x>=0; x--) {
			if(map[cctv.y][x] == 6)
				break;
			else 
				map[cctv.y][x] = -1;
		}
	}
	if(dir == 3) {
		for(int y=cctv.y-1; y>=0; y--) {
			if(map[y][cctv.x] == 6)
				break;
			else 
				map[y][cctv.x] = -1;
		}
	}

}

 

이차원 배열 백업

dfs 는 재귀호출 뒤 상태를 원복해주어야하기때문에 map 을 백업해둔 후, 재귀호출이 끝난 뒤 원복해주어야 한다.

이때, 유용하게 사용가능한 간단한 함수를 미리 구현해 두면 사용이 쉽다.

void map_copy(int desc[][10], int src[][10]) {
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			desc[i][j] = src[i][j];
}

void DFS(int cnt) {
	if(cnt == target) {
		// ...
		return;
	}

	for(int dir=0; dir<4; dir++) {
		map_copy(backup, map);
        ...
		DFS(cctv_index+1);
		map_copy(map, backup);
	}
}

---

전체 코드

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

using namespace std;

const int rot_size[] = {4, 2, 4, 4, 1}; // 카메라 별 회전 가능 케이스 수

struct CCTV {
	int y, x, no;
};
CCTV cctv[9];
int cctv_size;

int n, m;
int res = 987654321;
int map[10][10];

void update(int dir, CCTV cctv) {

	dir = (dir % 4);
	// 동남서북
	if(dir == 0) {
		for(int x=cctv.x+1; x<m; x++) {
			if(map[cctv.y][x] == 6)
				break;
			else 
				map[cctv.y][x] = -1;
		}
	}
	if(dir == 1) {
		for(int y=cctv.y+1; y<n; y++) {
			if(map[y][cctv.x] == 6)
				break;
			else 
				map[y][cctv.x] = -1;
		}
		
	}
	if(dir == 2) {
		for(int x=cctv.x-1; x>=0; x--) {
			if(map[cctv.y][x] == 6)
				break;
			else 
				map[cctv.y][x] = -1;
		}
	}
	if(dir == 3) {
		for(int y=cctv.y-1; y>=0; y--) {
			if(map[y][cctv.x] == 6)
				break;
			else 
				map[y][cctv.x] = -1;
		}
	}

}

void map_copy(int desc[][10], int src[][10]) {
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			desc[i][j] = src[i][j];
}

void DFS(int cctv_index) {

	if(cctv_index == cctv_size) {
		int candi = 0;
		
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++) {
				if(map[i][j] == 0)
					candi++;
			}
		}
		res = min(candi, res);
		return;
	}

	int backup[10][10] = {0,};
	int type = cctv[cctv_index].no;

	for(int dir=0; dir<rot_size[type]; dir++) {
		map_copy(backup, map);
		// 동남서북
		if(type == 0) {
			update(dir, cctv[cctv_index]);
		}
		if(type == 1) {
			update(dir, cctv[cctv_index]);
			update(dir+2, cctv[cctv_index]);
		}
		if(type == 2) {
			update(dir, cctv[cctv_index]);
			update(dir+1, cctv[cctv_index]);
		}
		if(type == 3) {
			update(dir, cctv[cctv_index]);
			update(dir+3, cctv[cctv_index]);
			update(dir+1, cctv[cctv_index]);
		}
		if(type == 4) {
			update(dir, cctv[cctv_index]);
			update(dir+1, cctv[cctv_index]);
			update(dir+2, cctv[cctv_index]);
			update(dir+3, cctv[cctv_index]);
		}
		DFS(cctv_index+1);
		map_copy(map, backup);
	}
}


int main() {

	scanf("%d %d", &n, &m);

	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++) {
			scanf("%d", &map[i][j]);
			if(map[i][j] != 0 && map[i][j] != 6) {
				cctv[cctv_size].y = i; 
				cctv[cctv_size].x = j;
				cctv[cctv_size].no = map[i][j]-1;
				cctv_size++;
			}
		}

	DFS(0);


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

}