[BOJ] 15683. 감시

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

15683번: 감시

CCTV구조체를 만들어서 CCTV의 좌표, 종류, 방향을 저장하게 했다.

방향은 나중에 모든 경우를 구해줄 때 저장한다.

모든 CCTV에 대해 방향을 정해줬으면 각 CCTV들의 감시 영역을 새로운 배열에 체크해주고

사각지대의 영역을 구해준다.

 

#include <iostream>
#include <vector>
using namespace std;
 
int n, m;
int ans;
int map[8][8];
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
 
struct CCTV {
    //감시카메라의 좌표
    int x;
    int y;
 
    //감시카메라 종류 번호
    int num;
 
    //감시할 방향 (나중에 정해준다)
    int dir;
    CCTV(int x, int y, int num) : x(x), y(y), num(num){}
};
 
vector<CCTV> vt;
 
 
//감시영역을 체크
void start(int x, int y, int dir, int newmap[8][8]) {
    while (true) {
        //dir 방향으로 계속 감시 영역을 표시한다.
        x += dx[dir];
        y += dy[dir];
 
        //범위 체크
        if (x < 0 || y < 0 || x >= n || y >= m) break;
        //벽이면 넘어갈 수 없다.
        if (map[x][y] == 6) break;
 
        //감시영역에 적당히 그냥 7넣어줬다.
        newmap[x][y] = 7;
    }
}
 
 
//모든 감시카메라들을 지정된 방향에 따라 감시영역을 표시한다.
int solve() {
    int newmap[8][8];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            newmap[i][j] = map[i][j];
        }
    }
 
    int vsize = vt.size();
    int x, y, num,dir;
    for (int i = 0; i < vsize; i++) {
        x = vt[i].x;
        y = vt[i].y;
        num = vt[i].num;
        dir = vt[i].dir;
 
        //종류에 따라서 감시영역을 표시한다.
        if (num == 1) {
            //한방향 감시
            start(x, y, dir, newmap);
        }
        else if (num == 2) {
            //반대방향이 두방향 감시
            start(x, y, dir, newmap);
            start(x, y, (dir+2)%4, newmap);
        }
        else if (num == 3) {
            //직각모양 두방향 감시
            start(x, y, dir, newmap);
            start(x, y, (dir+1)%4, newmap);
        }
        else if (num == 4) {
            //세방향 감시
            start(x, y, dir, newmap);
            start(x, y, (dir + 1) % 4, newmap);
            start(x, y, (dir + 2) % 4, newmap);
        }
        else if (num == 5) {
            //네 방향 모두 감시
            start(x, y, dir, newmap);
            start(x, y, (dir + 1) % 4, newmap);
            start(x, y, (dir + 2) % 4, newmap);
            start(x, y, (dir + 3) % 4, newmap);
        }
    }
 
 
    //처음에 사각지대였는데 감시영역을 표시한 이후에도 사각지대이면 cnt증가
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 0 && newmap[i][j] == 0) cnt++;
        }
    }
 
 
    //사각지대 수를 리턴
    return cnt;
}
 
 
//모든 감시카메라에 대해서 방향을 정해준다.
void select(int index) {
    if (index == vt.size()) {
        int tmp = solve();
 
        if (ans > tmp) ans = tmp;
        return;
    }
 
    for (int i = 0; i <= 3; i++) {
        vt[index].dir = i;
        select(index + 1);
    }
    
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
 
            //감시카메라이면 벡터에 넣는다.
            if (map[i][j] >= 1 && map[i][j] <= 5) {
                vt.push_back(CCTV( i,j,map[i][j] ));
            }
        }
    }
 
 
    //정답이 될 수 있는 값보다 큰 값을 미리 저장
    ans = 65;
    select(0);
 
    cout << ans << '\n';
 
    return 0;
}