백준 15683번: 감시 (C++)

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

문제를 보면, 카메라의 전체 개수가 8개로 많지 않다. 카메라의 종류별로 가능한 각도들을 모두 시뮬레이션해주면 되겠다.

각각의 카메라가 가질 수 있는 상태를 번호로 지정했다. 1번 카메라는 0~3번 상태, 2번 카메라는 4번~5번 상태... 이런 방식이다.

이제 카메라들이 띄고 있을 수 있는 상태를 조합으로 뽑아주면 된다.

이때 1번 카메라는 0~3번 밖에 쓸 수 없는 것처럼, 각 카메라별로 가능한 상태(인덱스)가 정해져 있기 때문에, 조합을 카메라에 대해서 먼저 해주고, 그리고 카메라의 상태에 대해서 이어서 해주어야한다.

작게 동, 서, 남, 북 방향으로 뻗어가는 방식인데, 카메라에 따라서 동시에 동서, 동남, 동서남 이런식으로 여러가지 상태를 가진다.

즉 동, 서, 남, 북 네가지 방향에 대한 처리만 정확하게 구현하면, 나머지는 그냥 그대로 코드를 사용하면 된다.

#include<iostream>
#include<vector>
 
using namespace std;
 
int R, C, map[10][10], tmp[10][10];
struct CAMPOS {
    int idx; //카메라 번호
    int r;
    int c;
};
vector<CAMPOS> cv;
bool isused[10][4]; //카메라 8개, 각도 사용 정보
bool masterUsage[9];
int cam[10][4]; //i번째 순서 카메라가 가질 수 있는 각도 저장
int arr[10], st = 0, st2 = 0, res = 100;
void init() {
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 4; j++)
            cam[i][j] = -1;
}
 
void process() {
    //arr에 카메라 각도 번호
    for (int i = 0; i < cv.size(); i++) {
        int cr = cv[i].r;
        int cc = cv[i].c;
        if (arr[i] == 0) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 1) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 2) {
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 3) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 4) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 5) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 6) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 7) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 8) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 9) {
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 10) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 11) {
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
        }
        else if (arr[i] == 12) {
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
        }
        else if (arr[i] == 13) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
        }
        else if (arr[i] == 14) {
            for (int j = cv[i].r + 1; j <= R - 1; j++) {//남
                if (map[j][cv[i].c] != 0 && map[j][cv[i].c] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[j][cv[i].c] == 6) break;
                if (map[j][cv[i].c] == 0) map[j][cv[i].c] = 7; //감시 가능 영역을 7
            }
            for (int j = cc - 1; j >= 0; j--) {//서
                if (map[cr][j] != 0 && map[cr][j] != 6) continue;
                if (map[cr][j] == 6) break;
                if (map[cr][j] == 0) map[cr][j] = 7;
            }
            for (int j = cr - 1; j >= 0; j--) {//북
                if (map[j][cc] != 0 && map[j][cc] != 6) continue;
                if (map[j][cc] == 6) break;
                if (map[j][cc] == 0) map[j][cc] = 7;
            }
            for (int j = cv[i].c + 1; j <= C - 1; j++) {//동
                if (map[cv[i].r][j] != 0 && map[cv[i].r][j] != 6) continue; //빈공간X and 벽X -> 카메라면 스킵
                if (map[cv[i].r][j] == 6) break;
                if (map[cv[i].r][j] == 0) map[cv[i].r][j] = 7; //감시 가능 영역을 7
            }
        }
    }
}
void backTracking(int k) {
    if (k == cv.size()) {
 
        process();
 
        //사각지대 계산
        int cnt = 0;
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (map[i][j] == 0) cnt++;
 
        if (res > cnt) 
            res = cnt;
 
        //원상복구
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                map[i][j] = tmp[i][j];
        return;
    }
 
    if (k == 0) st = 0;
 
    for (int i = st; i < cv.size(); i++) {
        if (!masterUsage[i]) {
            masterUsage[i] = true;
            //i번카메라가 사용중이 아니면서
            //if (k == 0) st2 = 0;
            for (int j = 0; j < 4; j++) {
                if (cam[i][j] != -1 && !isused[i][j]) {
                    //존재하는 카메라 각도이면서 사용중이 아닌 각도라면
                    arr[k] = cam[i][j];
                    isused[i][j] = true;
                    st = i;
                    //st2 = j;
                    backTracking(k + 1);
                    isused[i][j] = false;
                }
            }
            masterUsage[i] = false;
        }
 
    }
 
}
int main(void) {
    ios::sync_with_stdio(false);
 
    cin >> R >> C;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) {
            cin >> map[i][j];
            tmp[i][j] = map[i][j];
            if (map[i][j] != 0 && map[i][j] != 6) {
                CAMPOS tmp;
                tmp.r = i;
                tmp.c = j;
                tmp.idx = map[i][j];
                cv.push_back(tmp); //cv에 카메라 정보 저장
            }
        }
 
    init();
 
    for (int i = 0; i < cv.size(); i++) {
        if (cv[i].idx == 1) {
            for (int j = 0; j < 4; j++)
                cam[i][j] = j;
        }
        else if (cv[i].idx == 2) {
            for (int j = 0; j < 2; j++)
                cam[i][j] = j + 4;
        }
        else if (cv[i].idx == 3) {
            for (int j = 0; j < 4; j++)
                cam[i][j] = j + 6;
        }
        else if (cv[i].idx == 4) {
            for (int j = 0; j < 4; j++)
                cam[i][j] = j + 10;
        }
        else if (cv[i].idx == 5) {
            cam[i][0] = 14;
        }
    }
 
    backTracking(0);
    cout << res << '\n';
 
}