15683번: 감시 (BOJ C/C++)

15683번: 감시

사용 언어: C++

 

이번 문제는 내용이 길고 그림이 많다 보니 직접 백준 페이지를 확인하는 것이 좋을 것 같다.

 

풀이

저 sight 함수를 재귀로 만들어서 각 재귀마다 ans를 계산하는 풀이를 짜다가 그러면 자칫 잘못하면 재귀가 너무 많이 돌아갈 수 있고 sight 함수를 각 카메라마다 만들어줘야해서 복잡해져서 아래의 brute force 풀이인 for문을 4^Q.size만큼 돌리는 풀이로 바꿨다. 아래의 코드가 queue가 아닌 vector를 쓰면 매번 Q를 Q1으로 초기화 해줘야하는 번거로움이 줄어들 수 있다.

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

int board1[10][10];
int board2[10][10]; 
int ans;
int n, m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

queue<tuple<int,int,int>> Q; // x좌표, y좌표, cctv 번호
queue<tuple<int,int,int>> Q1; //Q1->Q, Q->Q1 복사할 큐

bool OOB(int a, int b){
    return a<0 || a>=n || b<0 || b>=m;
}

void sight(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;
        board2[x][y] = 7;
    }
}

void func(){
    //1 << (2*cctv.size())는 4의 cctv.size()승을 의미
    //tmp를 4진법으로 뒀을 때 각 자리수를 cctv의 방향으로 생각할 것이다.
    for(int tmp = 0; tmp < (1<<(2*Q.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;    
        while(!Q.empty()){
            int dir = brute % 4;
            brute /= 4;
            int x,y,cctv;
            tie(x,y,cctv) = Q.front(); Q.pop();
            switch(cctv){
                case 1:
                    sight(x,y,dir);
                    break;
                case 2:
                    sight(x,y,dir);
                    sight(x,y,dir+2);
                    break;
                case 3:
                    sight(x,y,dir);
                    sight(x,y,dir+1);
                    break;
                case 4:
                    sight(x,y,dir);
                    sight(x,y,dir+1);
                    sight(x,y,dir+2);
                    break;
                default:
                    sight(x,y,dir);
                    sight(x,y,dir+1);
                    sight(x,y,dir+2);
                    sight(x,y,dir+3);
                    break;
            }
        }
        int val = 0;
        for(int i = 0; i < n; i++)
          for(int j = 0; j < m; j++)
            val += (board2[i][j]==0);
        ans = min(ans, val);
        Q = Q1;
    }
}

int main(void){
    ios::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 >> board1[i][j];
            if(board1[i][j] && board1[i][j] != 6)    
                Q.push({i,j,board1[i][j]});
            if(!board1[i][j]) ans++;
        }
    }
    Q1 = Q;
    func();
    cout << ans << '\n';

    return 0;
}

queue가 아니고 vector