[BOJ] 15683 - 감시 (C++, 시뮬레이션) / 삼성 SW 역량테스트 기출

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

문제 링크

---

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int map[9][9];
int n,m;
//우 상 좌 하
int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1};

struct cctv{
    int y,x,num;
};

vector<cctv> cctvLst;

int cctvNum;
int mini = 99999999;
bool isRange(int y, int x){
    return y >= 0 && y < n && x >= 0 && x < m;
}
void check(int sy, int sx, int dir){
    int realdir = dir%4;
    int ny = sy;
    int nx = sx;
    while(isRange(ny + dy[realdir],nx + dx[realdir])){
        ny = ny + dy[realdir];
        nx = nx + dx[realdir];
        if(map[ny][nx] == 6){
            break;
        }
        if(map[ny][nx] == 0){
            map[ny][nx] = -1;
        }
    }
}

void dfs(int idx){
    if(idx == cctvNum){
        int result = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(map[i][j] == 0){
                    result ++;
                }
            }
        }
        mini = min(mini, result);
        return;
    }
    int save_map[9][9];
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            save_map[i][j] = map[i][j];
        }
    }
    for(int i=idx; i<cctvNum; i++){
        int cy = cctvLst[i].y;
        int cx = cctvLst[i].x;
        int cnum = cctvLst[i].num;
        for(int j=0; j<4; j++){
            if(cnum == 1){
                check(cy,cx,j);
            }
            else if(cnum == 2){
                check(cy,cx,j);
                check(cy,cx,j+2);
            }
            else if(cnum == 3){
                check(cy,cx,j);
                check(cy,cx,j+1);
            }
            else if(cnum == 4){
                check(cy,cx,j);
                check(cy,cx,j+1);
                check(cy,cx,j+2);
            }
            else if(cnum == 5){
                check(cy,cx,j);
                check(cy,cx,j+1);
                check(cy,cx,j+2);
                check(cy,cx,j+3);
            }

            dfs(i+1);
            for(int i1=0; i1<n; i1++){
                for(int j1=0; j1<m; j1++){
                    map[i1][j1] = save_map[i1][j1];
                }
            }
        }
    }
}
int main(){
    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){
                cctvLst.push_back({i,j,map[i][j]});
            }
        }
    }
    cctvNum = cctvLst.size();
    dfs(0);

    cout << mini << endl;
    return 0;
}

풀이 접근

1. n, m이 최대 8x8 까지이니 완탐 가능

2. cctv의 갯수가 최대 8개 까지이니 모든 cctv를 4방향 탐색 가능

3. cctv별로 탐색 가능 범위가 지정되어 있으니, dx, dy를 이용해 방향 지정만 잘 해주자

4. dfs 재귀에서 빠져나올때 마다 map을 복원해줘야 이전 state에서 활용 가능!

 

생각보다 간단한 문제였다.