[15683 번] 감시

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

15683번: 감시

 

BFS문제를 풀었을 때와 비슷하게 2차원을 표시하는 x,y표시를 dx[],dy[]를 이용하여서 0,1,-1을 활용하여 남,동,북,동쪽 방향을 나타내게 만들었습니다.

board1은 원본 board2는 cctv가 감시하는 구간을 0에서 7로 변경하면 내부 인덱스값을 바꾸면서 값을 넣는 배열로 만들었습니다. cctv 좌표를 저장할 vector변수를 만들어줍니다.

 

 

문제를 풀 때 특정 (x,y)좌표에서 dir 방향으로 진행하면서 벽 (6)을 만나기 전까지 지나치는 모든 0을 7로 바꾸기 위해서 upd라는 함수를 만들어 줍니다.

이때 동서남북 4방향이므로 cctv 감시 방향을 지정할 수 있도록 4진법을 써서 cctv 개수가 1개이면 경우의수는 4개, 2개면 16개, 3개는 64개 등과 같이 4진법을 이용하여서 표시해줍니다.

이떄 주의해야할 점이 벽을 만나거나 생성된 배열공간을 넘어가면 해당 함수는 종료가 되며 0이 아닌 cctv(1~5)를 만날경우에는 continue를 이용하여서 이후 진행을 하게 도와줍니다.

 

 

이제 main문에서는 mn이라는 변수에 초기 배열 공간을 설정할 때 있는 0의 개수를 저장함과 동시에 나중에 답으로 나올 사각 지대의 최소 크기를 만들어줍니다.

이후 반복문을 이용하여서 board1을 생성시키고 그에 해당하는 값을 넣습니다. 이때 각 위치에 넣는 값이 0이면 mn을 count하고,만약 cctv값을 입력할 경우 해당 좌표값을 cctv에 넣어줍니다.

 

※tmp를 4진법으로 둘 때 right shift를 이용해서 반복조건을 구현하는데 pow를 안쓰는 이유는 pow는 실수를 인자로 받아 실수를 반환하는 형태로 이번 문제와 같은 경우는 조건으로 주는 경우의 수가 작아 괜찮지만 3의 38승만 가더라도 계산 시간으로인해 1초를 오버하여 런타임에러가 발생할 수 있습니다. 따라서 비트 연산자를 이용하여서 4진법의 반복문을 for문을 통해 구현하였습니다.

 

이후 반복문을 이용해서 board2를 원본 board1의 내용과 복사를 하면서 tmp값을 임의의 변수 brute를 넣어 brute를 이용하여서 4로 나누며 4진법수를 dir에 저장시킵니다. dir은 방향을 나타내는 값으로 해당 dir을 인자로 받은 cctv의 x,y좌표를 보면 dx,dy값에서 찾을 수 있습니다. 이 값을 x,y 변수에 넣고 이제 board1을 확인해보면서 해당 cctv가 있을 시 upd함수를 cctv 특성에 맞게 조건문을 짜줍니다.

 

 

마지막으로 val이란 변수를 생성하여서 board2에 남은 0의 개수를 저장한 후 mn과 min함수로 비교하여서 작은 값을 mn을 저장시켜주고 반복문을 마치면 mn값이 답이되게 됩니다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; // 남쪽, 동쪽, 북쪽, 서쪽 순서
int n, m;
int board1[10][10]; 
int board2[10][10]; 
vector<pair<int,int> > cctv; 

bool OOB(int a, int b){ // Out Of Bounds 확인
  return a < 0 || a >= n || b < 0 || b >= m;
}

// (x,y)에서 dir 방향으로 진행하면서 벽을 만날 때 까지 지나치는 모든 빈칸을 7로 바꿔버림
void upd(int x, int y, int dir){
  dir %= 4;
  while(1){
    x += dx[dir];
    y += dy[dir];
    if(OOB(x,y) || board2[x][y] == 6) return; 
    if(board2[x][y] != 0) continue;
    board2[x][y] = 7; 
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  int mn = 0;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> board1[i][j];
      if(board1[i][j] != 0 && board1[i][j] != 6)
        cctv.push_back({i,j});
      if(board1[i][j] == 0) mn++;
    }
  }
  // 1 << (2*cctv.size())는 4의 cctv.size()승을 의미.
  for(int tmp = 0; tmp < (1<<(2*cctv.size())); tmp++){
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        board2[i][j] = board1[i][j];
    int brute = tmp;    
    for(int i = 0; i < cctv.size(); i++){
      int dir = brute % 4;
      brute /= 4;
      int x = cctv[i].X;
      int y = cctv[i].Y;
      if(board1[x][y] == 1){
        upd(x,y,dir);
      }
      else if(board1[x][y] == 2){
        upd(x,y,dir);
        upd(x,y,dir+2);
      }
      else if(board1[x][y] == 3){
        upd(x,y,dir);
        upd(x,y,dir+1);
      }
      else if(board1[x][y] == 4){
        upd(x,y,dir);
        upd(x,y,dir+1);
        upd(x,y,dir+2);
      }
      else{ // board1[x][y] == 5
        upd(x,y,dir);
        upd(x,y,dir+1);
        upd(x,y,dir+2);
        upd(x,y,dir+3);
      }
    }
    int val = 0;
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        val += (board2[i][j]==0);
    mn = min(mn, val);
  }
  cout << mn;
}