BJ15683 감시

2020.02.10

감시

Solution

• Input 자료 저장 : inMap을 양쪽으로 2칸씩 여유있게 선언해놓고 4방향을 6(벽)으로 덮어서 만들고 시작했다.
• 알고리즘 : 기본적으로 CCTV의 기준 방향을 완전탐색을 이용해 정하고 방향이 모두 정해졌을 때의 사각지대의 크기를 모두 비교하여 최소 크기를 리턴하는 방식
  • getResult 함수 : idx번째부터 끝까지 CCTV의 basis direction을 선택하는 재귀구조의 완전탐색 함수
  • getSize 함수 : 방향을 모두 선택한 getResult 함수의 기저조건에서 detectMap에 CCTV탐색을 각 방향과 CCTV의 종류에 따라 탐색하도록 만들었고 탐색이 완료된 후에 사각지대의 크기를 구하고 다시 detectMap을 초기화하여 사각지대의 크기를 return 하는 함수
  • detecting 함수 : y,x,dir을 이용해서 탐색하는 구문이 반복적으로 사용되는 것을 간단하게 만들기 위해 기준 좌표로 부터 방향으로 탐색하는 함수

//! 2020.02.10
// TODO BJ15683_감시
#include <cstdio>
#include <vector>

using namespace std;

const int MAX = 15;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,-1,0,1};
int N,M;
int inMap[MAX][MAX];
int detectMap[MAX][MAX];
vector <pair<int,int>> CCTV;
vector <int> dirCCTV;

void detecting(int y,int x,int dir){
    while(inMap[y][x]!=6){
        detectMap[y][x] = 1;
        y+=dy[dir];
        x+=dx[dir];
    }
}

int getSize(){
    int cnt = 0;

    for(int i=0;i<dirCCTV.size();i++){
        int y = CCTV[i].first;
        int x = CCTV[i].second;
        int numCCTV = inMap[y][x];

        switch(numCCTV){
            case 1:
                detecting(y,x,dirCCTV[i]);
                break;
            case 2:
                detecting(y,x,dirCCTV[i]);
                detecting(y,x,dirCCTV[i]+2);
                break;
            case 3:
                for(int dir=0;dir<2;dir++){
                    int nextDir = (dir+dirCCTV[i])%4;
                    detecting(y,x,nextDir);
                }
                break;
            case 4:
                for(int dir=0;dir<4;dir++){
                    if(dir==dirCCTV[i]) continue;
                    detecting(y,x,dir);
                }
                break;
            case 5:
                for(int dir=0;dir<4;dir++) detecting(y,x,dir);
                break;
        }
    }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(inMap[i][j]!=6 && detectMap[i][j]==0) cnt++;
            detectMap[i][j] = 0;
        }
    }
    return cnt;
}

int getResult(int idx){
    if(idx>=dirCCTV.size()){
        return getSize();
    }
    else{
        int y = CCTV[idx].first;
        int x = CCTV[idx].second;
        int numCCTV = inMap[y][x];
        int minResult = 987654321;
        if(numCCTV==2){
            for(int i=0;i<2;i++){
                dirCCTV[idx] = i;
                int tmp = getResult(idx+1);
                if(tmp<minResult) minResult = tmp;
            }
        }else if(numCCTV==5){
            int tmp = getResult(idx+1);
            if(tmp<minResult) minResult = tmp;
        }else{
            for(int i=0;i<4;i++){
                dirCCTV[idx] = i;
                int tmp = getResult(idx+1);
                if(tmp<minResult) minResult = tmp;
            }
        }
        return minResult;
    }
}

int main(){
    scanf("%d %d",&N,&M);
    for(int i=0;i<=N+1;i++){
        inMap[i][0] = 6;
        inMap[i][M+1] = 6;
    }
    for(int j=0;j<=M+1;j++){
        inMap[0][j] = 6;
        inMap[N+1][j] = 6;
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            scanf("%d",&inMap[i][j]);
            if(inMap[i][j]!=0 && inMap[i][j]!=6){
                CCTV.push_back(make_pair(i,j));
                dirCCTV.push_back(0);
            }
        }
    }
    printf("%d\n",getResult(0));
    return 0;
}

실수 : 방향을 넣어주는 for loop에서 같은 변수를 사용하다보니 for loop에 사용되는 변수가 변화하는 문제가 생겼다. 변수관리를 명확히 해줄 필요가 있을 것 같다.