백준 15683 감시

브루트 포스 문제입니다.

 

5가지 종류의 cctv가 있고 이 cctv는 벽이 없다면 해당방향을 감시 할 수 있게 됩니다. 각 주어진 cctv는 회전하여 설치가 가능할 때 사각지대의 최대 영역을 구하는 문제입니다.

 

따라서 각 cctv가 탐지 할 수 있는 부분을 90도씩 회전해서 감시해보고 각 상태에서 사각지대 영역을 구해서 답을 구하면 됩니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <vector>

using namespace std;

int cctv[10][10];
int N,M;

vector<pair<int ,int> > pos;
int c1[4] = {1,0,0,0}; //상좌하우
int c2[4] = {1,0,1,0};
int c3[4] = {1,1,0,0};
int c4[4] = {1,1,1,0};
int c5[4] = {1,1,1,1};
int ans = 987654321;

void checkfunc(int cnum[4], int cur[10][10], int x, int y) { //감시 영역 check

    for(int i = 0; i < 4; i++) {
        if(cnum[i] == 1) {
            if(i==0) {
               for(int k = x-1; k >= 0; k--) {
                    if(cur[k][y] == 6) break;
                    if(cur[k][y] == 0) cur[k][y] = -1;
               }
            }
            else if(i==1) {
                for(int k = y-1; k >= 0; k--) {
                    if(cur[x][k] == 6) break;
                    if(cur[x][k] == 0) cur[x][k] = -1;
                }
            }
            else if(i==2) {
                for(int k  = x+1; k < N; k++) {
                    if(cur[k][y] == 6) break;
                    if(cur[k][y] == 0) cur[k][y] = -1;
                }
            }
            else if(i==3) {
                for(int k = y+1; k < M; k++) {
                    if(cur[x][k] == 6) break;
                    if(cur[x][k] == 0) cur[x][k] = -1;
                }
            }
        }
    }
    return;
}

void dfs(int cur[10][10], int cnt) {

    if(cnt == pos.size()) {
        int curnum = 0;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++) {
                if(cur[i][j] == 0) curnum++;
            }

        ans = min(ans, curnum);
        return;
    }

    int i = pos[cnt].first;
    int j = pos[cnt].second;

    int cpcctv[4];
    int curcctv = cctv[i][j];

    if(curcctv == 1) {
        for(int m = 0; m < 4; m++) cpcctv[m] = c1[m];
    }
    else if(curcctv == 2) {
        for(int m = 0; m < 4; m++) cpcctv[m] = c2[m];
    }
    else if(curcctv == 3) {
        for(int m = 0; m < 4; m++) cpcctv[m] = c3[m];
    }
    else if(curcctv == 4) {
        for(int m = 0; m < 4; m++) cpcctv[m] = c4[m];
    }
    else if(curcctv == 5) {
        for(int m = 0; m < 4; m++) cpcctv[m] = c5[m];
    }

    for(int k = 0; k < 4; k++) {

        if(k==1&&curcctv==5) break;
        if(k==2&&curcctv==2)break;

        int temp = cpcctv[3];
        cpcctv[3] = cpcctv[2];
        cpcctv[2] = cpcctv[1];
        cpcctv[1] = cpcctv[0];
        cpcctv[0] = temp;

        int cp[10][10];

        for(int a = 0; a < N; a++)
            for(int b = 0; b < M; b++)
                cp[a][b] = cur[a][b];

        checkfunc(cpcctv, cp, i, j);
        dfs(cp, cnt+1);
    }
    return;
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N >> M;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++) {
            cin >> cctv[i][j];
            if(cctv[i][j] >= 1 && cctv[i][j] <= 5) pos.push_back({i, j});
        }

    dfs(cctv, 0);
    cout<<ans;
    return 0;
}