[C++] 백준 15683번 - 감시

생각보다 엄청 더러웠던(?) 문제였다.

역시 브루트포스는 항상 그렇고 그렇다......

 

CCTV 구조체를 하나 만들어서 CCTV 종류(몇번인지), 몇열, 몇행에 저장되어있는지에 대한 정보를 저장하고

rotation이라는 정수 배열에서 회전 가능한 범위를 넣어주었다.

 

디버깅을 하면 이제 input 하고 dfs로 탐색이 들어가는데,

이제 중요한점은 백트랙킹을 해야한다는 것이다.

이 문제의 핵심인 부분이다.

예를 들어서 

01000

00000

00000

00000

00000

이런 cctv가 있으면, 얘는 아래쪽으로 탐색을 해야 하는 것이다

그래서 이 부분에 대해서 각각의 경우에 대해서 백트랙킹을 해주면 된다. 

 

#include <iostream>
#define MAX 8
using namespace std;

struct CCTV {
    int type, r, c;
};

int N, M, ans = 99999999;
int map[MAX][MAX];
int cctv_size;
CCTV cctv[MAX];
const int rotation[] = { NULL, 4, 2, 4, 4, 1 };

void map_copy(int desc[MAX][MAX], int src[MAX][MAX]) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            desc[i][j] = src[i][j];
}

void update(int dir, CCTV cctv) {
    dir %= 4;
    if (dir == 0) {
        for (int c = cctv.c + 1; c < M; c++) {
            if (map[cctv.r][c] == 6) break;
            map[cctv.r][c] = -1;
        }
    }
    else if (dir == 1) {
        for (int r = cctv.r - 1; r >= 0; r--) {
            if (map[r][cctv.c] == 6) break;
            map[r][cctv.c] = -1;
        }
    }
    else if (dir == 2) {
        for (int c = cctv.c - 1; c >= 0; c--) {
            if (map[cctv.r][c] == 6) break;
            map[cctv.r][c] = -1;
        }
    }
    else if (dir == 3) {
        for (int r = cctv.r + 1; r < N; r++) {
            if (map[r][cctv.c] == 6) break;
            map[r][cctv.c] = -1;
        }
    }
}

void DFS(int cctv_idx) {
    if (cctv_idx == cctv_size) {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0)
                    cnt++;
            }
        }
        if (ans > cnt)
            ans = cnt;
        return;
    }

    int backup[8][8];
    int type = cctv[cctv_idx].type;

    for (int dir = 0; dir < rotation[type]; dir++) {
        map_copy(backup, map); //back tracking

        if (type == 1) {
            update(dir, cctv[cctv_idx]);
        }
        else if (type == 2) {
            update(dir, cctv[cctv_idx]);
            update(dir + 2, cctv[cctv_idx]);
        }
        else if (type == 3) {
            update(dir, cctv[cctv_idx]);
            update(dir + 1, cctv[cctv_idx]);
        }
        else if (type == 4) {
            update(dir, cctv[cctv_idx]);
            update(dir + 1, cctv[cctv_idx]);
            update(dir + 2, cctv[cctv_idx]);
        }
        else if (type == 5) {
            update(dir, cctv[cctv_idx]);
            update(dir + 1, cctv[cctv_idx]);
            update(dir + 2, cctv[cctv_idx]);
            update(dir + 3, cctv[cctv_idx]);
        }

        DFS(cctv_idx + 1);
        
        map_copy(map, backup);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    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] != 0 && map[i][j] != 6) {
                cctv[cctv_size].r = i;
                cctv[cctv_size].c = j;
                cctv[cctv_size].type = map[i][j];
                ++cctv_size;
            }
        }
    }

    DFS(0);

    cout << ans << '\n';
    return 0;
}