백준 15683번 - 감시

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

위의 문제를 해결하기 위해 DFS 방식을 이용하여

매번 호출 할 때마다 사무실의 상태를 업데이트해서 cctv의 개수 만큼 함수를 돌면

사각 지대의 최소값을 확인해주도록 했다.

DFS를 이용했지만 시뮬레이션 문제로 느껴질 만큼 구현하기 위한 코드양이 많았다.

먼저 vector를 이용해 처음 입력값을 받을 때  cctv종류와 y, x좌표를 저장했다.

다음으로 DFS 함수를 호출하게 되면

cctv의 개수 만큼 DFS 함수를 호출 했는지 확인한 후에 사각 지대의 최소값을 업데이트 해준다.

아직 확인해야할 cctv가 남아있다면, 현재 확인하려는 cctv 종류와 y,x좌표를 가져온 후에 cctv의 종류에 따라 감시를 시작한다.

감시를 하기 위해 cctv 종류와 y,x좌표를 move 함수에 전달해서 

동,서,남,북 각각의 방향에 따라 cctv를 감시할 수 있도록 했다.

cctv로 해당 지점을 확인했을 때 -1로 표기했다.

DFS함수를 호출할 때마다 사무실의 상태를 업데이트 할 때 중요한 점은

각각의 방향에 따라 감시를 완료한 후에 다른 방향을 감시할 때 업데이트 된 사무실을 확인하면 안되는 것이다.

예를 들어 cctv가 1번일 때

동쪽을 감시한 뒤에 다음 DFS함수를 호출하여 확인하는 작업이 이루어졌다고 가정하자.

그 다음으로 남쪽을 감시한 뒤에 다음 DFS를 호출하기 위해서는 동쪽으로 감시를 완료한 사무실로 확인 하면 안되는 것이다.

이를 위해 이전 사무실 값을 저장한 다음에 다른 방향을 감시할 때 이전 값을 이용해서 확인하도록 했다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
struct str{
    int cctv; //cctv 종류
    int y; //cctv y좌표
    int x; //cctv x좌표
    str(int cctv,int y,int x):cctv(cctv),y(y),x(x){};
};
 
int N,M;
int ans=100; //사각 지대 최소값
int cctv_cnt=0; //cctv 개수
vector<vector<int>> map(8,vector<int>(8,0)); //사무실
vector<str> vec;
 
void move(int dir,int y,int x){
    
    switch(dir){
        
        //북
        case 0:
            for(int i=y-1;i>=0;i--){
                if(map[i][x]==6) break;
                if(map[i][x]==0) map[i][x]=-1; //cctv 감시 완료
            }
            break;
        
        //동
        case 1:
            for(int j=x+1;j<M;j++){
                if(map[y][j]==6) break;
                if(map[y][j]==0) map[y][j]=-1; 
            }
            break;
            
        //남
        case 2:
            if(dir==2){
                for(int i=y+1;i<N;i++){
                    if(map[i][x]==6) break;
                    if(map[i][x]==0) map[i][x]=-1;
                }
            }
            break;
            
        //서
        case 3:
            for(int j=x-1;j>=0;j--){
                if(map[y][j]==6) break;
                if(map[y][j]==0) map[y][j]=-1;
            }
            
    }
 
}
 
void dfs(int step){
    
    if(step==cctv_cnt){
        
        int cnt=0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(map[i][j]==0)
                    cnt++;
            }
        }
        
        ans=min(ans,cnt);
        return;
    }
    
    int cctv=vec[step].cctv;
    int y=vec[step].y;
    int x=vec[step].x;
    
    //이전에 확인한 사무실 상태값 저장
    vector<vector<int>> map2=map;
    
    switch(cctv){
        
        case 1:
            //북,동,남,서
            for(int dir=0;dir<4;dir++){
                move(dir,y,x);
                dfs(step+1);
                
                map=map2;
            }
            break;
            
        case 2:
            //북남,동서
            for(int dir=0;dir<2;dir++){
                move(dir,y,x);
                move(dir+2,y,x);
                dfs(step+1);
                
                map=map2;
            }
            break;
            
        case 3:
            //북동,동남,남서,서북
            for(int dir=0;dir<4;dir++){
                move(dir,y,x);
                move((dir+1)%4,y,x);
                dfs(step+1);
                
                map=map2;
            }
            break;
        
        case 4:
            //북동남,동남서,남서북,서북동
            for(int dir=0;dir<4;dir++){
                move(dir,y,x);
                move((dir+1)%4,y,x);
                move((dir+2)%4,y,x);
                dfs(step+1);
                
                map=map2;
            }
            break;
            
        case 5:
            for(int dir=0;dir<4;dir++)
                move(dir,y,x);
            
            dfs(step+1);
    }
    
}
 
 
int main(){
    
    cin>>N>>M;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            scanf("%d",&map[i][j]);
            if(map[i][j]!=0 && map[i][j]!=6){
                cctv_cnt++;
                vec.push_back(str(map[i][j],i,j));
            }
        }
    }
    
    dfs(0);
    cout<<ans<<endl;
    
    return 0;
}