BOJ 15683) 감시 (C++)

15683번: 감시

 각 CCTV의 좌표를 arr배열에 저장하고 가능한 모든 경우를 탐색한다. 5번 카메라는 한 방향, 2번 카메라는 2 방향, 나머지 카메라는 4 방향으로 설치가 가능하다. 

 풀면서 한가지 실수 때문에 시간을 많이 허비했다. 처음에 각 CCTV가 감시하는 공간을 -1로 체크하고 되돌아오면서 0으로 다시 복구시켜 준 것이다. 이렇게 할 경우 다른 CCTV와 같은 공간을 감시하다가 한 CCTV만 다른 방향으로 트는 경우에 해당 공간에 대한 감시가 풀린 것으로 체크된다. 그래서 이후에는 감시하는 공간인 경우 (기존 값)-1을, 감시를 해제하는 경우 (기존값)+1을 해줌으로써 해당 문제를 해결했다.

 정말 단순하게 구현해서 풀고 나서도 코드가 그리 마음에 들지 않는다. 중복되거나 쓸모없는 케이스(CCTV가 사무실 바깥 방향을 )가 포함되는 경우도 있는데 사무실의 크기가 작고 CCTV도 8대가 최대라 시간안에 통과할 수 있었다. 좀 더 효율적인 방법이 있는지 알아봐야겠다.

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define x first
#define y second

int office[8][8];
int arr[8][8];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
pii cctv[10];
int N, M, cnt, ans=64;
void count(){
  int temp=0;
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      if(arr[i][j]==0){
        temp++;
      }
    }
  }
  if(temp<ans){
    ans=temp;
  }
}

void one(int a, int b, int n,bool tf){
  int nx=a+dx[n];
  int ny=b+dy[n];
  if(tf){
    while(nx>=0&&nx<N&&ny>=0&&ny<M){
      if(arr[nx][ny]==6) break;
      if(arr[nx][ny]<1) arr[nx][ny]-=1;
      nx+=dx[n]; 
      ny+=dy[n];
    }
  } else {
    while(nx>=0&&nx<N&&ny>=0&&ny<M){
      if(arr[nx][ny]==6) break;
      if(arr[nx][ny]<0) arr[nx][ny]+=1;
      nx+=dx[n]; 
      ny+=dy[n];
    }
  }
}

void two(int a, int b, int n, bool tf){
  one(a, b, n, tf);
  one(a,b, (n+1)%4, tf);
}

void three(int a, int b, int n, bool tf){
  if(n==0){
    one(a,b,0, tf);
    one(a,b,2, tf);
  }else if(n==1){
    one(a,b,0, tf);
    one(a,b,3, tf);
  } else if(n==2){
    one(a,b,1, tf);
    one(a,b,2, tf);
  } else if(n==3){
    one(a,b,1, tf);
    one(a,b,3, tf);
  }
}

void four(int a, int b, int n, bool tf){
  one(a,b,n, tf);
  one(a,b,(n+1)%4, tf);
  one(a,b,(n+2)%4, tf);
}

void five(int a, int b, bool tf){
  one(a,b,0, tf);
  one(a,b,1, tf);
  one(a,b,2, tf);
  one(a,b,3, tf);
}

void dir(int n){
  if(n==cnt){
    count();
    return ;
  }
  int nx=cctv[n].x;
  int ny=cctv[n].y;
  if(arr[nx][ny]==1){
    for(int i=0;i<4;i++){
      one(nx,ny,i,1);
      dir(n+1);
      one(nx,ny,i,0);
    }
  } else if (arr[nx][ny]==2){
    for(int i=0;i<2;i++){
      two(nx,ny,2*i,1);
      dir(n+1);
      two(nx,ny,2*i,0);
    }
  } else if (arr[nx][ny]==3){
    for(int i=0;i<4;i++){
      three(nx,ny,i,1);
      dir(n+1);
      three(nx,ny,i,0);
    }
  } else if (arr[nx][ny]==4){
    for(int i=0;i<4;i++){
      four(nx,ny,i,1);
      dir(n+1);
      four(nx,ny,i,0);
    }
  } else if (arr[nx][ny]==5){
      five(nx,ny,1);
      dir(n+1);
      five(nx,ny,0);
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin>>N>>M;

  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      cin>>arr[i][j];
      if(arr[i][j]>0&&arr[i][j]<6){
        cctv[cnt]={i,j};
        cnt++;
      }
    }
  }

  dir(0);
  cout<<ans;
  return 0;
}