[BOJ] 15683 감시

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

15683번: 감시

구현문제인데 푸는데 너무 오래 걸렸다.

결국 모든 경우의 수를 다 따져야 하기 때문에 효율적으로 구현하기 보다는 빠르게 구현하는데 초점을 두어야 한다.

구현 문제는 결국 집중력 싸움이라는 것을 잊지말자 ㅎ

#include <iostream>
#include <vector>
using namespace std;

int N,M,s;
int map[8][8];
vector<pair<int,int > > v;
int res=100;

void up_count(int y,int x){
    while(y>=0&&map[y][x]!=6){
        if(map[y][x]<=0){
            map[y][x]--;
        }
        y--;
    }
}

void down_count(int y,int x){
    while(y<N&&map[y][x]!=6){
        if(map[y][x]<=0){
            map[y][x]--;
        }
        y++;
    }
}

void left_count(int y, int x){
    while(x>=0&&map[y][x]!=6){
        if(map[y][x]<=0){
            map[y][x]--;
        }
        x--;
    }
}

void right_count(int y,int x){
    while(x<M&&map[y][x]!=6){
        if(map[y][x]<=0){
            map[y][x]--;
        }
        x++;
    }
}

void intialize_up(int y,int x){
    while(y>=0&&map[y][x]!=6){
        if(map[y][x]<=-1){
            map[y][x]++;
        }
        y--;
    }
}

void intialize_down(int y,int x){
    while(y<N&&map[y][x]!=6){
        if(map[y][x]<=-1){
            map[y][x]++;
        }
        y++;
    }
    
}

void intialize_left(int y,int x){
    while(x>=0&&map[y][x]!=6){
        if(map[y][x]<=-1){
            map[y][x]++;
        }
        x--;
    }
}

void intialize_right(int y,int x){
    while(x<M&&map[y][x]!=6){
        if(map[y][x]<=-1){
            map[y][x]++;
        }
        x++;
    }
}

void cal(int n){
    if(n==s){
        int cnt=0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(map[i][j]==0) cnt++;
            }
        }
        res=min(cnt,res);
        return;
    }
    
    int y=v[n].first, x=v[n].second;
    if(map[y][x]==1){
        up_count(y-1,x);
        cal(n+1);
        intialize_up(y-1,x);
        
        down_count(y+1,x);
        cal(n+1);
        intialize_down(y+1,x);
        
        left_count(y,x-1);
        cal(n+1);
        intialize_left(y,x-1);
        
        right_count(y,x+1);
        cal(n+1);
        intialize_right(y,x+1);
        
    }else if(map[y][x]==2){
        up_count(y-1,x);
        down_count(y+1,x);
        cal(n+1);
        intialize_up(y-1,x);
        intialize_down(y+1,x);
        
        left_count(y,x-1);
        right_count(y,x+1);
        cal(n+1);
        intialize_left(y,x-1);
        intialize_right(y,x+1);
        
    }else if(map[y][x]==3){
        up_count(y-1,x);
        right_count(y,x+1);
        cal(n+1);
        intialize_up(y-1,x);
        intialize_right(y,x+1);
        
        right_count(y,x+1);
        down_count(y+1,x);
        cal(n+1);
        intialize_right(y,x+1);
        intialize_down(y+1,x);
        
        down_count(y+1,x);
        left_count(y,x-1);
        cal(n+1);
        intialize_down(y+1,x);
        intialize_left(y,x-1);
        
        left_count(y,x-1);
        up_count(y-1,x);
        cal(n+1);
        intialize_left(y,x-1);
        intialize_up(y-1,x);
        
    }else if(map[y][x]==4){
        up_count(y-1,x);
        right_count(y,x+1);
        down_count(y+1,x);
        cal(n+1);
        intialize_up(y-1,x);
        intialize_right(y,x+1);
        intialize_down(y+1,x);
        
        right_count(y,x+1);
        down_count(y+1,x);
        left_count(y,x-1);
        cal(n+1);
        intialize_right(y,x+1);
        intialize_down(y+1,x);
        intialize_left(y,x-1);
        
        down_count(y+1,x);
        left_count(y,x-1);
        up_count(y-1,x);
        cal(n+1);
        intialize_down(y+1,x);
        intialize_left(y,x-1);
        intialize_up(y-1,x);
        
        left_count(y,x-1);
        right_count(y,x+1);
        up_count(y-1,x);
        cal(n+1);
        intialize_left(y,x-1);
        intialize_right(y,x+1);
        intialize_up(y-1,x);
        
    }else if(map[y][x]==5){
        //4방향
        left_count(y,x-1);
        right_count(y,x+1);
        up_count(y-1,x);
        down_count(y+1,x);
        cal(n+1);
        intialize_left(y,x-1);
        intialize_right(y,x+1);
        intialize_up(y-1,x);
        intialize_down(y+1,x);
    }
}


int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    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&&map[i][j]!=0) v.push_back(make_pair(i,j));
        }
    }
    
    s=v.size();
    
    cal(0);
    cout<<res;
    return 0;
}