백준 15683 (감시)

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

15683번: 감시

해당 문제는 각 CCTV 당 최대 4개의 경우의 수를 가질 수 있다. 따라서 map을 탐색하며 CCTV 가 존재할 경우 해당 CCTV가 감시할 수 있는 모든 경우의 수를 탐색하면 되는 문제이다. 

재귀의 흐름을 보면 다음과 같다.

 위와 같이 탐색 된 CCTV의 종류 별로 나올 수 있는 모든 경우의 수를 탐색하며 탐색되는 영역을 visit 배열에 체크하며 재귀를 수행하면 문제를 해결할 수 있다.

#include <iostream>
#include <cstring>

using namespace std;
int maxx = 10000;
int map[8][8];
int visit[8][8];
int my, mx;
int cctvCnt;
int used[8];

int check[4][2] = {
	-1, 0,
	0, +1,
	+1, 0,
	0, -1
};

int getMax(){
	int cnt = 0;

	for (int i = 0; i < my; ++i){
		for (int j = 0; j < mx; ++j){
			if (visit[i][j] == 0 && map[i][j] != 6){
				++cnt;
			}
		}
	}

	return cnt;
}

void checkMap(int y, int x, int dir){
	// 주의사항
    // visit 배열 check시 오직 map의 요소가 6일때 즉 벽일때 감시를 중단한다.
    // 만약 visit[dy][dx] == 1 인 경우는 cctv 가 있거나 기존에 감시하던 영역을 의미함으로
    // 다음 영역을 감시할 수 있음

	if (dir == 3){
		int f = 1;
	}
	int dy = y + check[dir][0];
	int dx = x + check[dir][1];

	if (dy >= 0 && dx >= 0 && dy < my && dx < mx && map[dy][dx] != 6){
		if (map[dy][dx] == 0){
			visit[dy][dx] = 1;
		}
		while (1){
			int ty = dy + check[dir][0];
			int tx = dx + check[dir][1];
			if (ty >= 0 && tx >= 0 && ty < my && tx < mx && map[ty][tx] != 6){
				if (map[ty][tx] == 0){
					visit[ty][tx] = 1;
				}
				dy += check[dir][0];
				dx += check[dir][1];
			}
			else break;
		}
	}

	return;
}

void spin(int y, int x, int dir, int num){
	int tmp = 0;
	if (num == 1){
		checkMap(y, x, dir);
	}

	if (num == 2){
		// 0 : 2 || 1 : 3

		for (int i = dir; i <= dir + 2; i += 2){
			if (i > 3) tmp = i - 4;
			else tmp = i;
			checkMap(y, x, tmp);
		}
	}

	if (num == 3){
		for (int i = dir; i < dir + 2; ++i){
			if (i > 3) tmp = i - 4;
			else tmp = i;
			checkMap(y, x, tmp);
		}
	}

	if (num == 4){
		for (int i = dir; i <= dir + 2; ++i){
			if (i > 3) tmp = i - 4;
			else tmp = i;
			checkMap(y, x, tmp);
		}
	}

	if (num == 5){
		for (int i = 0; i < 4; ++i){
			checkMap(y, x, i);
		}
	}

}

void dfs(int level){
	
	int m = getMax();
	if (m < maxx) maxx = m;
	

	int cpMap[8][8];

	for (int i = 0; i< my; ++i){
		for (int j = 0; j < mx; ++j){
        	// map을 탐색하며 check 되지 않은 CCTV 일 경우 재귀호출
			if (map[i][j] >= 1 && map[i][j] < 6 && visit[i][j] == 0){
				visit[i][j] = 1;
				memcpy(cpMap, visit, 4 * 8 * 8);
				for (int c = 0; c < 4; ++c){
					spin(i, j, c, map[i][j]);
					dfs(level + 1);
					memcpy(visit, cpMap, 4 * 8 * 8);
				}
			}
		}
	}
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> my >> mx;
	int cpmap[8][8];
	memcpy(cpmap, visit, 4 * 8 * 8);

	for (int i = 0; i < my; ++i){
		for (int j = 0; j < mx; ++j){
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < my; ++i){
		for (int j = 0; j < mx; ++j){
			if (map[i][j] >= 1 && map[i][j] < 6){
				++cctvCnt;
			}
		}
	}
	dfs(0);
	printf("%d", maxx);

}