백준 15683 감시 C++

[문제 링크]

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

[입출력 예]

입력	출력
4 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 6 0 0 0 0 0 0 0	20

[소스코드]

#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){
    return a< 0 || a>=n || b< 0 || b>=m;
}

// 위치와 방향을 주면, "그 다음 점부터" 비어있으면 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;
    }
}


// 정보 입력 받아 board1에 저장
// mn을 전체 0의 개수로 초기화
// 총 경우의 수는 4방향 ^ 카메라 대수임.
// 그 경우의 수에 대해 for문으로 돌려야 하고, 각 카메라 방향 4진법 변환하듯 얻을 수 있음.
// i개의 방향과 i개의 cctv 위치가 주어졌으므로 for문을 통해 upd함수로 7로 칠함 (0이 사각지대)
// 한 케이스 내에서 모든 cctv에 upd를 적용했을 때 남은 0의 개수와 현재 mn을 비교, 갱신
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++){ // tmp를 4진법으로 뒀을 때 각 자리수를 cctv의 방향으로 생각할 것이다.
    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; // tie(x, y) = cctv[i];로 쓰면 1줄로 줄일 수 있음
      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;
}

[ 출처 ]

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/15683.cpp