백준 15683 - 감시

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

15683번: 감시

문제 설명

---

사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다. 

 

RULE

- 총 5개의 CCTV 가 존재하는데, 각 CCTV 는 감시할 수 있는 방향이 다르다.

- CCTV 는 90도 회전이 가능하다.

- CCTV 는 벽을 통과할 수 없지만, CCTV 는 통과할 수 있다.

 

 

 

* 1번 CCTV - (오른쪽), (위쪽), (왼쪽), (아래쪽) => 4가지

* 2번 CCTV - (왼쪽, 오른쪽), (위쪽, 아래쪽) => 2가지

* 3번 CCTV - (위쪽, 오른쪽), (오른쪽, 아래쪽), (아래쪽, 왼쪽), (왼쪽, 위쪽) => 4가지

* 4번 CCTV - (왼쪽, 위쪽, 오른쪽), (위쪽, 오른쪽, 아래쪽), (오른쪽, 아래쪽, 왼쪽), (아래쪽, 왼쪽, 위쪽) => 4가지

* 5번 CCTV - (왼쪽, 위쪽, 오른쪽, 아래쪽) => 1가지

 

 

 

접근 방법

---

위의 룰을 기반으로 Dfs와 Brute Focefh 차근차근 구현했습니다. 구현에 까다롭지는 않지만 그렇다고 쉽지는 않다고 생각합니다.

좋은 문제인거 같아요 화이팅~

 

 

코드

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

typedef struct{
    int y,x;
    int dir;
    int type;
}Camera;
vector<Camera>vec;
vector<Camera>vec_temp;
int r,c;
vector<vector<int> >map(8,vector<int>(8,0));
int numofCam,ans=100;
// int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; //동-남-서-북

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<c;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<r;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 count){
    if(count==numofCam){
        int cnt=0;
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(map[i][j]==0)cnt++;
            }
        }
        ans = min(ans,cnt);
        return;
    }
    int cury = vec[count].y;
    int curx = vec[count].x;
    int curtype = vec[count].type;
    
    vector<vector<int> >map_temp = map;
    switch (curtype){

        case 1:
            for(int dir=0;dir<4;dir++){
                move(dir,cury,curx);
                dfs(count+1);
                map=map_temp;
            }
            break;
        case 2:
            for(int dir=0;dir<4;dir++){
                move(dir,cury,curx);
                move(dir+2,cury,curx);
                dfs(count+1);
                map=map_temp;
            }
            break;
        case 3:
            for(int dir=0;dir<4;dir++){
                move(dir,cury,curx);
                move((dir+1)%4,cury,curx);
                dfs(count+1);
                map=map_temp;
            }
            break;
        case 4:
            for(int dir=0;dir<4;dir++){
                move(dir,cury,curx);
                move((dir+1)%4,cury,curx);
                move((dir+2)%4,cury,curx);
                dfs(count+1);
                map=map_temp;

            }
            break;
        case 5:
            for(int dir=0;dir<4;dir++){
                move(dir,cury,curx);
            }
            dfs(count+1);
            break;
    }
    

}
int main(){
    cin>>r>>c;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin>>map[i][j];
            if(map[i][j]>=1 && map[i][j]<=5){
                Camera cam;
                cam.y= i; cam.x =j;
                cam.dir = 0;
                cam.type = map[i][j];
                vec.push_back(cam);
            }
        }
    }
    numofCam =vec.size();
    dfs(0);
    cout<<ans<<"\n";
    return 0;
}

funny algorithm ^-^