15683 감시

cctv 최대 여덟개, 맵 최대크기 8*8이 제한조건이다.

사각지대를 최소화 할 수 있도록 cctv가 향하는 방향을 결정하고 사각지대의 최소크기를 출력하는 문제다.

방향 5가지, 총 8대이고 맵이 8*8이니 dfs를 한다면

정도가 나올것이다. 시간제한은 1초이기 때문에 넉넉한 편이다.

이 문제는 dfs로 풀 수 있는 문제라는걸 떠올리는건 어렵지 않지만 실수하기가 쉬운 문제다.

1. 일단 cctv 종류에 따라 모양이 일정하지 않아 일일이 다 코딩해야 하고

2. 감시범위가 겹쳐지는 경우를 실수하기 쉬우며

3. 백트래킹처럼 하다보면 check배열이나 맵에 마킹해놓은것을 지우지 않거나 잘못된 것을 지우기 십상이라서 그렇다.

#include <stdio.h>
 
int n, m, a[8][8], all_cnt, ans;
int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
int cx[8], cy[8], c_idx;
 
void f(int cx, int cy, int *qx, int *qy, int &q_idx, int i) {
    int nx = cx;
    int ny = cy;
    i%=4;
    while (nx + dx[i] >= 0 && ny + dy[i] >= 0 && nx + dx[i] < n && ny + dy[i] < m && a[nx + dx[i]][ny + dy[i]] != 6) {
        nx += dx[i]; ny += dy[i];
        if (a[nx][ny] == 0) {
            a[nx][ny] = -1;
            qx[q_idx] = nx; 
            qy[q_idx++] = ny;
        }
    }
}
 
void dfs(int d, int cnt) {
    if (d == c_idx) {
        ans = ans > all_cnt - cnt ? all_cnt - cnt : ans;
        return;
    }
    int type = a[cx[d]][cy[d]];
    if (type == 1) {
        int qx[15], qy[15], q_idx;
        for (int i = 0; i < 4; i++) {
            q_idx = 0;
            f(cx[d], cy[d], qx, qy, q_idx, i);
            dfs(d + 1, cnt + q_idx);
            while (q_idx--) a[qx[q_idx]][qy[q_idx]] = 0;
        }
    }
    else if (type == 2) {
        int qx[15], qy[15], q_idx;
        for (int i = 0; i < 2; i++) {
            q_idx = 0;
            for (int j = 0; j < 4; j += 2) 
                f(cx[d], cy[d], qx, qy, q_idx, i + j);
            dfs(d + 1, cnt + q_idx);
            while (q_idx--) a[qx[q_idx]][qy[q_idx]] = 0;
        }
    }
    else if (type == 3) {
        int qx[15], qy[15], q_idx = 0;
        for (int i = 0; i < 4; i += 2) {
            q_idx = 0;
            f(cx[d], cy[d], qx, qy, q_idx, i);
            for (int j = 1; j < 4; j += 2) {
                int nq_idx = q_idx;
                f(cx[d], cy[d], qx, qy, nq_idx, i + j);
                dfs(d + 1, cnt + nq_idx);
                while (nq_idx-- > q_idx)
                    a[qx[nq_idx]][qy[nq_idx]] = 0;
            }
            while (q_idx--) a[qx[q_idx]][qy[q_idx]] = 0;
        }
    }
    else if (type == 4) {
        int qx[4][15], qy[4][15], q_idx[4] = { 0, }, all_idx = 0;
        for (int i = 0; i < 4; i++) {
            f(cx[d], cy[d], qx[i], qy[i], q_idx[i], i);
            all_idx += q_idx[i];
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < q_idx[i]; j++) 
                a[qx[i][j]][qy[i][j]] = 0;
            dfs(d + 1, cnt + all_idx - q_idx[i]);
            for (int j = 0; j < q_idx[i]; j++) 
                a[qx[i][j]][qy[i][j]] = -1;
        }
        for (int i = 0; i < 4; i++) for (int j = 0; j < q_idx[i]; j++)
            a[qx[i][j]][qy[i][j]] = 0;
    }
    else if (type == 5) {
        int qx[4][15], qy[4][15], q_idx[4] = { 0, }, all_idx = 0;
        for (int i = 0; i < 4; i++) {
            f(cx[d], cy[d], qx[i], qy[i], q_idx[i], i);
            all_idx += q_idx[i];
        }
        dfs(d + 1, cnt + all_idx);
        for (int i = 0; i < 4; i++) for (int j = 0; j < q_idx[i]; j++)
            a[qx[i][j]][qy[i][j]] = 0;
    }
}
 
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
        scanf("%d", &a[i][j]);
        if (a[i][j] == 0) all_cnt++;
        else if (a[i][j] != 6) cx[c_idx] = i, cy[c_idx++] = j;
    }
    ans = all_cnt;
    dfs(0, 0);
    printf("%d\n", ans);
    return 0;
}