[개쉬운 풀이] 백준 15683 감시 CPP (11일차)

 

문제

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

 

생각

1. 먼저, CCTV의 최대 갯수가 8개 이므로 각각의 CCTV 방향을 모두 고려해서 해결해야하는 완전탐색 문제이다.

2. 여기서 CCTV가 감지한 부분을 처음에는 단순하게 #처리 하려고 했지만, 백트래킹하는 과정에서 #이 겹치고 삭제되면서 오류가 발생할 수 있다는 것을 인지하였다.

3. 따라서 isVisited를 통해 +1과 -1을 하는 방식으로 진행하였다.

4. CCTV는 CCTV를 통과할 수 있으며, CCTV는 일직선으로 탐지하고 각 타입에 따라 방향이 다르다.

5. 즉, 일직선으로 탐지하는 코드 하나에 각 타입별로 탐지 코드를 넣어서 작성하였다.

6. 마지막 출력을 진행할때, isVisited가 0이고 map에서 0인 부분을 count해주었다. -> isVisited는 cctv도 0으로 처리할 가능성이 있기 때문.

 

풀이

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

const int MAP_MAX = 9;

struct T {
    int x, y;
    int type;
};

int N, M;
int map[MAP_MAX][MAP_MAX];
int isVisited[MAP_MAX][MAP_MAX];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int answer = 1e9;
vector<T> cctvs;

void input(){
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> map[i][j];
            if(map[i][j] != 0) isVisited[i][j] = -1;
            if(map[i][j] != 0 && map[i][j] != 6){
                T tmp;
                tmp.x = i;
                tmp.y = j;
                tmp.type = map[i][j];
                cctvs.push_back(tmp);
            }
        }
    }
}

//벽 판별
bool isWall(int x, int y){
    if(map[x][y] == 6) return true;
    return false;
}

//영역 밖 판별
bool isOut(int x, int y){
    return x < 1 || y < 1 || x > N || y > M;
}

//cctv의 탐지 과정
void process(T cctv, int dir, bool on){
    int nx = cctv.x;
    int ny = cctv.y;
    
    while(true){
        nx += dx[dir];
        ny += dy[dir];
        if(isWall(nx, ny) || isOut(nx,ny)) break;
        if(on) isVisited[nx][ny] += 1;
        else isVisited[nx][ny] -= 1;
    }
}

void type1(T cctv, int dir, bool on){
    process(cctv, dir, on);
}

void type2(T cctv, int dir, bool on){
    process(cctv, dir, on);
    process(cctv, (dir+2)%4, on);
}

void type3(T cctv, int dir, bool on){
    process(cctv, dir, on);
    process(cctv, (dir+1)%4, on);
}

void type4(T cctv, int dir, bool on){
    for(int i = 0; i < 3; i++){
        dir = (dir+i) % 4;
        process(cctv, dir, on);
    }
}

void type5(T cctv, int dir, bool on){
    for(int i = 0; i < 4; i++){
        dir = (dir+i) % 4;
        process(cctv, dir, on);
    }
}

//cctv의 종류 판별
void getType(T cctv, int i, bool on){
    switch (cctv.type)
        {
        case 1:
            type1(cctv, i, on);
            break;
        case 2:
            type2(cctv, i, on);
            break;
        case 3:
            type3(cctv, i, on);
            break;
        case 4:
            type4(cctv, i, on);
            break;
        case 5:
            type5(cctv, i, on);
            break;
        default:
            break;
        }
}

void print(){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cout << isVisited[i][j] << " ";
        }
        cout << endl;
    }
}

int getSpace(){
    int res = 0;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(isVisited[i][j] == 0 && map[i][j] == 0){
                res++;
            }
        }
    }

    return res;
}

void sol(int idx){
    //cctv를 모두 판독한 이후
    if(idx == cctvs.size()){
        int res = getSpace();
        answer = min(answer, res);
        return;
    }
    T cctv = cctvs[idx];
    for(int i = 0; i < 4; i++){
        getType(cctv, i, true); //탐지
        sol(idx+1);
        getType(cctv, i, false); //탐지 해제
    }
}

int main(){
    input();
    sol(0);
    cout << answer << endl;
    return 0;
}