[BOJ] 15683. 감시

#include<iostream>
#include<vector>
#include<cstring>
#define p pair<int,int>
using namespace std;

/*
 0번째는 빈칸
 cctv가 1번 일 경우 : 총 4번
 cctv가 2번 일 경우 : 총 2번
 cctv가 3번 일 경우 : 총 4번
 cctv가 4번 일 경우 : 총 4번
 cctv가 5번 일 경우 : 총 1번
 */
int dir_size[] ={ 0,4,2,4,4,1 };

// 동 서 남 북
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int map[8][8];
int v[8][8];

int ans;
int wall_size;
int n,m;

struct Node{
    int x;
    int y;
    int dir;
    Node(int a, int b, int c): x(a), y(b), dir(c) {};
};

vector<Node> cctv;

bool inRange(int x, int y){
    if( x < 0 || x >= n || y < 0 || y >= m)
        return false;
    return true;
}

void fill(int idx, int dir, int value){
    int nx = cctv[idx].x;
    int ny = cctv[idx].y;
    v[nx][ny] = 1;
    while (1) {
        nx = nx + dx[dir];
        ny = ny + dy[dir];
        if(! inRange(nx, ny) || map[nx][ny] == 6)
            break;
        /*
         일반적으로 DFS 백트래킹에서
         visit 체크는 1 or 0으로 초기화한다.
         // visit = 1
         // dfs();
         // visti = 0과 같은 구조
         
         그런데 여기선 그렇게 하면 안된다.
         만약 (2,2) 지점을
         우선 (2,1)에서 우측으로 살핀 후
         그 다음 (2,3)에서 좌측으로 감시한다고 할 때
         
         (2,2)는 두 곳 지점에서 감시하고 있기 때문에
         단지 1 or 0으로 했을 경우엔
         나중에 호출된 (2,3)에서 해당 위치를 0으로 초기화해버리면
         (2,1)에서 감시하는 영역까지 없애버리는 경우가 발생된다.
         그렇기 때문에
         v[nx][ny]++ or v[nx][ny]-- 와 같이 처리를 해서
         v[nx][ny] == 0이라면 감시하지 않는 영역이라고 볼 수 있고
         v[nx][ny] >= 1이라면 감시하고 있는 영역이라고 볼 수 있다.
         */
        v[nx][ny] += 1 * value;
    }
}

void fill_list(int idx, vector<int> v, int value){
    int size = (int) v.size();
    for(int i=0; i<size; i++){
        fill(idx,v[i],value);
    }
}

void dfs(int idx){
    if(idx == (int)cctv.size()){
        int cnt = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(v[i][j] == 0){
                    cnt ++;
                }
            }
        }
        /*
         v배열에서 0인 값을 찾을 때
         이미 벽인 좌표에 대해서도 +를 해준다.
         그렇기 때문에 벽의 수만큼 cnt에서 빼야한다.
         */
        cnt -= wall_size;
        ans = ans < cnt ? ans : cnt;
        return ;
    }
    
    int size = (int) dir_size[ cctv[idx].dir ];
    for(int i=0; i<size; i++){
        vector<int> v;
        
        if(cctv[idx].dir == 1){
            v.push_back(i);
            fill_list(idx, v , 1);
            dfs(idx+1);
            fill_list(idx, v , -1);
        }
        else if(cctv[idx].dir == 2){
            if( i == 0){
                v.push_back(0); v.push_back(1);
                fill_list(idx, v , 1);
                dfs(idx+1);
                fill_list(idx, v , -1);
            }
            else if( i == 1){
                v.push_back(2); v.push_back(3);
                fill_list(idx, v , 1);
                dfs(idx+1);
                fill_list(idx, v , -1);
            }
        }
        else if(cctv[idx].dir == 3){
            if( i == 0){
                v.push_back(0); v.push_back(3);
                fill_list(idx, v , 1);
                dfs(idx+1);
                fill_list(idx, v , -1);
            }
            else if( i == 1){
                v.push_back(1); v.push_back(3);
                fill_list(idx, v , 1);
                dfs(idx+1);
                fill_list(idx, v , -1);
            }
            else if( i == 2){
                v.push_back(1); v.push_back(2);
                fill_list(idx, v , 1);
                dfs(idx+1);
                fill_list(idx, v , -1);
            }
            else if( i == 3){
                v.push_back(0); v.push_back(2);
                fill_list(idx, v , 1);
                dfs(idx+1);
                fill_list(idx, v , -1);
            }
        }
        else if(cctv[idx].dir == 4){
            if( i == 0){
                v.push_back(0); v.push_back(2); v.push_back(3);
                fill_list(idx, v , 1);
                dfs(idx+1);
                fill_list(idx, v , -1);
            }
            else if( i == 1){
                v.push_back(0); v.push_back(1); v.push_back(3);
                fill_list(idx, v , 1);
                dfs(idx+1);
                fill_list(idx, v , -1);
            }
            else if( i == 2){
                v.push_back(1); v.push_back(2); v.push_back(3);
                fill_list(idx, v , 1);
                dfs(idx+1);
                fill_list(idx, v , -1);
            }
            else if( i == 3){
                v.push_back(0); v.push_back(1); v.push_back(2);
                fill_list(idx, v , 1);
                dfs(idx+1);
                fill_list(idx, v , -1);
            }
        }
        else{
            v.push_back(0); v.push_back(1); v.push_back(2); v.push_back(3);
            fill_list(idx, v , 1);
            dfs(idx+1);
            fill_list(idx, v , -1);
        }
    }
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ans = 2e9;
    
    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] == 6)
                wall_size ++;
            else if(map[i][j] != 0){
                cctv.push_back( Node(i,j,map[i][j]) );
            }
        }
    }
    
    dfs(0);
    
    cout << ans << endl;
    return 0;
}