[BOJ15683] 감시
[BOJ15683] 감시
문제 설명
-
CCTV는 종류가 5가지가 있고, 각각의 CCTV는 감시할 수 있는 방법이 다르다. 각각의 CCTV를 설치할 때는 회전을 90도로 하며 설치할 수 있다 (그림 출처 : 백준 온라인 저지).
-
CCTV는 감시할 수 있는 방법에 따라 그 방향을 감시하며, CCTV끼리는 통과할 수 있으며, 벽을 만나면 그 이상은 감시하지 못한다.
-
필드의 모양과 설치된 CCTV 위치와 종류가 주어질 때, 감시할 수 없는 사각지대의 최소 개수를 구하는 문제이다.
코드 리뷰
-
멘탈이 나갔다.. 시간도 오래걸리고 코드도 너무 길다. 다음에 꼭 다시 생각하고 풀어봐야겠다.
-
먼저 벡터를 통해, 필드를 탐색하면서 CCTV의 좌표 및 종류를 벡터에 넣어서, CCTV의 개수를 파악한다.
-
CCTV는 1번은 4가지, 2번은 2가지, 3번은 4가지, 4번은 4가지, 5번은 1가지의 가지수로 설치 할 수 있다. 이 가지수를 모두 탐색하는 방법으로 풀었다.
-
두번째로, 배열 첫번째에 들어있는 CCTV부터 탐색을 하여, 처음 저장된 방향으로 맵에 표시하고, 두번째 CCTV로 재귀를 이용하여 들어간다. 체크 맵은 3차원 배열로 저장하여, 몇번째 CCTV까지 봤는지 누적으로 체크한다.
-
CCTV 개수만큼 DFS를 하고 나면, 마지막 맵에 대해 남아있는 0의 개수를 세고, MIN 함수와 비교하여 작은 값을 저장하는 식으로 해결하였다.
-
재귀를 한번 리턴하면, 그 전 단계의 체크배열을 가져온 후 그 단계에 대해서 다시 CCTV가 보는 맵을 체크한다.
/*BOJ15683 감시*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef struct {
int x;
int y;
int cctv_num;
}cctv_info;
int N, M;
int board[10][10];
int check[10][10][10];
int ans = 0;
int MAX = 10000000;
void all_search(vector <cctv_info> &cctv,int idx, int n) {
if (idx == n) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (check[n][i][j] == 0 && board[i][j]==0) ans++;
}
}
MAX = min(MAX, ans);
ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
check[n][i][j] = 0;
}
}
return;
}
if (cctv[idx].cctv_num == 1) {
for (int i = 1; i <= 4; i++) {
if (i == 1) {
for (int k = cctv[idx].y; k < M; k++) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx + 1][n][m] = check[idx][n][m];
}
}
all_search(cctv, idx + 1, n);
if (idx == 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = 0;
}
}
}
if (idx > 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = check[idx - 1][n][m];
}
}
}
}
else if (i == 2) {
for (int k = cctv[idx].x; k < N; k++) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx + 1][n][m] = check[idx][n][m];
}
}
all_search(cctv, idx + 1, n);
if (idx == 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = 0;
}
}
}
if (idx > 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = check[idx - 1][n][m];
}
}
}
}
else if (i == 3) {
for (int k = cctv[idx].y; k >= 0; k--) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx + 1][n][m] = check[idx][n][m];
}
}
all_search(cctv, idx + 1, n);
if (idx == 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = 0;
}
}
}
if (idx > 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = check[idx - 1][n][m];
}
}
}
}
else if (i == 4) {
for (int k = cctv[idx].x; k >=0; k--) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx + 1][n][m] = check[idx][n][m];
}
}
all_search(cctv, idx + 1, n);
if (idx == 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = 0;
}
}
}
if (idx > 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = check[idx - 1][n][m];
}
}
}
}
}
}
else if (cctv[idx].cctv_num == 2) {
for (int i = 1; i <= 2; i++) {
if (i == 1) {
for (int k = cctv[idx].x; k < N; k++) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int k = cctv[idx].x; k >= 0; k--) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx + 1][n][m] = check[idx][n][m];
}
}
all_search(cctv, idx + 1, n);
if (idx == 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = 0;
}
}
}
if (idx > 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = check[idx - 1][n][m];
}
}
}
}
else if (i == 2) {
for (int k = cctv[idx].y; k < M; k++) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int k = cctv[idx].y; k >= 0; k--) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx + 1][n][m] = check[idx][n][m];
}
}
all_search(cctv, idx + 1, n);
if (idx == 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = 0;
}
}
}
if (idx > 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = check[idx - 1][n][m];
}
}
}
}
}
}
else if (cctv[idx].cctv_num == 3) {
for (int i = 1; i <= 4; i++) {
if (i == 1) {
for (int k = cctv[idx].x; k < N; k++) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int k = cctv[idx].y; k < M; k++) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx + 1][n][m] = check[idx][n][m];
}
}
all_search(cctv, idx + 1, n);
if (idx == 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = 0;
}
}
}
if (idx > 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = check[idx - 1][n][m];
}
}
}
}
else if (i == 2) {
for (int k = cctv[idx].x; k < N; k++) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int k = cctv[idx].y; k >= 0; k--) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx + 1][n][m] = check[idx][n][m];
}
}
all_search(cctv, idx + 1, n);
if (idx == 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = 0;
}
}
}
if (idx > 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = check[idx - 1][n][m];
}
}
}
}
else if (i == 3) {
for (int k = cctv[idx].x; k >= 0; k--) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int k = cctv[idx].y; k < M; k++) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx + 1][n][m] = check[idx][n][m];
}
}
all_search(cctv, idx + 1, n);
if (idx == 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = 0;
}
}
}
if (idx > 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = check[idx - 1][n][m];
}
}
}
}
else if (i == 4) {
for (int k = cctv[idx].x; k >= 0; k--) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int k = cctv[idx].y; k >= 0; k--) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx + 1][n][m] = check[idx][n][m];
}
}
all_search(cctv, idx + 1, n);
if (idx == 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = 0;
}
}
}
if (idx > 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = check[idx - 1][n][m];
}
}
}
}
}
}
else if (cctv[idx].cctv_num == 4) {
for (int i = 1; i <= 4; i++) {
if (i == 1) {
for (int k = cctv[idx].x; k < N; k++) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int k = cctv[idx].x; k >= 0; k--) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int k = cctv[idx].y; k < M; k++) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx + 1][n][m] = check[idx][n][m];
}
}
all_search(cctv, idx + 1, n);
if (idx == 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = 0;
}
}
}
if (idx > 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = check[idx - 1][n][m];
}
}
}
}
else if (i == 2) {
for (int k = cctv[idx].x; k < N; k++) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int k = cctv[idx].x; k >= 0; k--) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int k = cctv[idx].y; k >=0; k--) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx + 1][n][m] = check[idx][n][m];
}
}
all_search(cctv, idx + 1, n);
if (idx == 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = 0;
}
}
}
if (idx > 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = check[idx - 1][n][m];
}
}
}
}
else if (i == 3) {
for (int k = cctv[idx].y; k < M; k++) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int k = cctv[idx].y; k >= 0; k--) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int k = cctv[idx].x; k < N; k++) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx + 1][n][m] = check[idx][n][m];
}
}
all_search(cctv, idx + 1, n);
if (idx == 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = 0;
}
}
}
if (idx > 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = check[idx - 1][n][m];
}
}
}
}
else if (i == 4) {
for (int k = cctv[idx].y; k < M; k++) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int k = cctv[idx].y; k >= 0; k--) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int k = cctv[idx].x; k >= 0; k--) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx + 1][n][m] = check[idx][n][m];
}
}
all_search(cctv, idx + 1, n);
if (idx == 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = 0;
}
}
}
if (idx > 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = check[idx - 1][n][m];
}
}
}
}
}
}
else if (cctv[idx].cctv_num == 5) {
for (int k = cctv[idx].x; k < N; k++) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int k = cctv[idx].x; k >= 0; k--) {
if (board[k][cctv[idx].y] == 6) break;
check[idx][k][cctv[idx].y] = 1;
}
for (int k = cctv[idx].y; k < M; k++) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int k = cctv[idx].y; k >= 0; k--) {
if (board[cctv[idx].x][k] == 6) break;
check[idx][cctv[idx].x][k] = 1;
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx + 1][n][m] = check[idx][n][m];
}
}
all_search(cctv, idx + 1, n);
if (idx == 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = 0;
}
}
}
if (idx > 0) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
check[idx][n][m] = check[idx - 1][n][m];
}
}
}
}
}
int main() {
scanf("%d%d", &N, &M);
int cnt = 0;
vector <cctv_info> cctv;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
scanf("%d", &board[i][j]);
if (board[i][j] == 1 || board[i][j] == 2 || board[i][j] == 3 || board[i][j] == 4 || board[i][j] == 5) {
cctv.push_back({ i,j,board[i][j] });
}
}
}
int n = cctv.size();
all_search(cctv,0,n);
printf("%d", MAX);
return 0;
}
댓글남기기