[백준 15683] 감시, C++

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

15683번: 감시

본 문제는 주어진 cctv를 회전하여 사각지대의 최솟값을 구하는 문제다. cctv는 총 5가지가 존재하여 회전은 4방향으로 가능하다. 따라서, cctv의 위치를 vector에 저장하고 cctv가 회전할 수 있는 모든 경우의 수를 확인하면 된다. 모든 경우의 수는 4방향으로 회전이 가능하기 때문에 4^(cctv 개수)의 경우의 수가 발생한다. 따라서 1 << ( 2*cctv.size() ) 만큼 탐색하면 된다. 마지막으로 cctv의 사각지대이면서 벽이 아닌곳의 개수를 구하면 된다.

#include <cstdio>
#include <vector>
#include <cstring>
 
using namespace std;
 
int map[9][9];
bool chk[9][9];
 
// 위 오른쪽 아래 왼쪽
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
 
vector<pair<int, int>> cctv;
 
int n, m;
 
void solution(int x, int y, int dir) {
    dir %= 4;
    while (true) {
        chk[x][y] = true;
        x += dx[dir];
        y += dy[dir];
        if (x < 0 || x >= n || y < 0 || y >= m) break;
        if (map[x][y] == 6) break;
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] != 0 && map[i][j] != 6) {
                cctv.push_back(make_pair(i, j));
            }
        }
    }
 
    int ans = n*m;
    for (int tmp = 0; tmp < (1<<(2*cctv.size())); tmp++) {
        int brute = tmp;
        memset(chk, false, sizeof(chk));
 
        for (int i = 0; i < cctv.size(); i++) {
            int dir = brute % 4;
            brute /= 4;
            int x = cctv[i].first;
            int y = cctv[i].second;
            if (map[x][y] == 1) {
                solution(x, y, dir);
            }
            else if (map[x][y] == 2) {
                solution(x, y, dir);
                solution(x, y, dir+2);
            }
            else if (map[x][y] == 3) {
                solution(x, y, dir);
                solution(x, y, dir+1);
            }
            else if (map[x][y] == 4) {
                solution(x, y, dir);
                solution(x, y, dir+1);
                solution(x, y, dir+3);
            }
            else if (map[x][y] == 5) {
                solution(x, y, dir);
                solution(x, y, dir+1);
                solution(x, y, dir+2);
                solution(x, y, dir+3);
            }
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!chk[i][j] && map[i][j] != 6) cnt += 1;
            }
        }
 
        if (ans > cnt) ans = cnt; 
    }
    printf("%d\n", ans);
}