[15683번] 감시

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

15683번: 감시

문제접근법

1. 카메라들의 위치와 방향을 기억할 자료 구조를 선언한다. 카메라들의 조합을 확인해가면서, 감시되는 지역을 체크하고 남은 사각 지대의 최솟값을 구한다.

 

2. 카메라들의 조합을 확인할 때, 백트래킹으로 하나 카메라마다 감시 지역을 추가할 수도 있고, 카메라의 방향을 모두 지정한 뒤에, 모든 카메라의 감시 지역을 확인할 수 있다. 이번 코드에서는, 후자의 방법을 사용했다.

 

유의사항

1. CCTV는 CCTV를 통과해서 감시할 수 있다.

 

2. 체크가 안되지만, 벽인 지형은 감시 지역이 아니다. 

 

1번과 2번을 유의해서 문제를 풀어야 한다. 예제를 하나씩 머릿속이나 노트로 그려가면서 문제를 푸는 것을 추천한다.

 

해설코드(C++)

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef struct camera {
    int r, c, dir;
    camera(int _r, int _c, int _dir) : r(_r), c(_c), dir(_dir) {};
}camera;
 
int N, M;
int map[9][9];
// 상 우 하 좌
int op[6][4] = { {},{0,0,0,1},{0, 1, 0, 1}, {1,1,0,0},{1,1,0,1 },{1,1,1,1} };
int mov[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int answer = 0;
int total = 0;
int comb[9] = { 0 };
vector<camera> v;
 
void dfs(int idx) {
    if (idx == v.size()) {
        int result = 0;
        int check[9][9];
        memset(check, 0, sizeof(check));
 
        // Checking
        for (int i = 0; i < v.size(); i++) {
            int t_op[4];
            int c_idx = v.at(i).dir;
            int r = v.at(i).r;
            int c = v.at(i).c;
            check[r][c] = 1;
 
            memcpy(t_op, op[c_idx], sizeof(t_op));
 
            // ROTATE
            for (int t = 0; t <= comb[i]; t++) {
                int tmp = t_op[3];
                for (int i = 3; i >= 1; i--)
                    t_op[i] = t_op[i - 1];
                t_op[0] = tmp;
            }
 
            // CCTV
            for (int o = 0; o < 4; o++) {
                if (t_op[o] == 1) {
                    int n_r = r;
                    int n_c = c;
                    while (1) {
                        n_r += mov[o][0];
                        n_c += mov[o][1];
 
                        if (n_r < 1 || n_c < 1 || n_r > N || n_c > M || map[n_r][n_c] == 6) break;
 
                        check[n_r][n_c] = 1;
                    }
                }
            }
        }
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (map[i][j] != 6 && check[i][j] == 0)
                    result += 1;
            }
        }
 
        answer = min(answer, result);
        return;
    }
 
    if (v.at(idx).dir == 1 || v.at(idx).dir == 3 || v.at(idx).dir == 4) {
        for (int i = 0; i < 4; i++) {
            comb[idx] = i;
            dfs(idx + 1);
        }
    }
    else if (v.at(idx).dir == 2) {
        for (int i = 0; i < 2; i++) {
            comb[idx] = i;
            dfs(idx + 1);
        }
    }
    else if (v.at(idx).dir == 5) {
        comb[idx] = 0;
        dfs(idx + 1);
    }
 
    return;
}
int main(void) {
    freopen("input.txt", "r", stdin);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
            if (map[i][j] >= 1 && map[i][j] <= 5)
                v.push_back(camera(i, j, map[i][j]));
 
            if (map[i][j] == 0) {
                answer++;
                total++;
            }
        }
    }
 
    // DFS
    dfs(0);
 
    cout << answer << endl;
    return 0;
}