[백준/C++] 15683번 감시

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

15683번: 감시

오랜만에 푼 구현 + 브루트 포스 + 백트래킹 문제이다.

문제 자체는 크게 까다롭지 않지만, 백트래킹에서 고민을 좀 많이 하였고 결국 다른 글을 참고하게 되었다..(시무룩)

1. 입력을 받는다 (CCTV가 나오면 해당 좌표를 벡터에 담아준다!)

2. 완전 탐색을 실시한다.

3-1. 만약 모든 CCTV를 확인하여, 감시 구역을 정했으면 사각지대의 수를 세서 최솟값을 저장한다.

3-2. 아니라면, num번째 CCTV의 좌표를 가져온다. (num = 1,2,3 즉 3개의 CCTV가 있다고 치자.) 그렇다면 첫번째  CCTV의 감시구역을 저장할 배열을 하나 마련한다. (코드 상에서 store배열)

- 회전은 90도씩 총 4번 가능하므로, 4번의 회전에 대해 탐색한다. 이 때 방향벡터를 이용하여 감시 구역을 탐색한다. (그림을 보면 1번 CCTV는 상,하,좌,우만 가능하고 2번 CCTV는 상하, 좌우가 가능하다. 3번 CCTV는 우상, 좌상, 우하, 우상이 가능하고 4번 CCTV는 좌우상, 상하좌, 좌우하, 상하우가 가능하고 5번은 그냥 상하좌우를 한번에 다 감시)

- 첫번째 CCTV를 일단 어느 한 방향에 대해 탐색이 끝나면, 다음 CCTV를 불러와서 또 어느 한 방향에 대해 탐색을 해준다. 첫번째 탐색 결과는 arr 배열에 저장되어 있고, 재귀호출을 하고난 후, 첫번째 CCTV의 감시구역(arr)을 store에 저장한다. 이를 두번째 CCTV에 대해 탐색에 활용한다! 두번째 CCTV는 store를 불러와서 탐색 후 다음 CCTV에 대한 재귀호출을 한다. 그리고 arr배열을 store에 저장해준다.  마찬가지로 3번째 CCTV도 2번째 CCTV까지의 탐색결과인 store를 arr에 불러와서 탐색 후, 다음 CCTV를 호출하는데 3번째가 마지막이기 때문에 3-1번을 수행한다. 1 -> 1 -> 1,2,3,4 => 1 -> 2 -> 1,2,3,4 => 1 -> 3-> 1,2,3,4 ... 이런식으로 탐색 하는 것이다. (1~4를 방향이라고 했을 때)

- 그리고 return이 되면, 3번째 CCTV를 for문을 돌려서 4방향에 대해 탐색한다. 이때 불러오는 store는 2번째 CCTV에 대해 탐색이 끝나고 그 정보를 저장해둔 배열이다!

* store가 지역변수인 이유?  재귀호출에 따라서 스택에는 지역변수도 같이 들어가는데, n번째 호출에서 store는 n-1번째 CCTV의 탐색이 끝났을 때 그 때 당시의 정보를 들고 있는 배열이기 때문에 지역변수로 사용해주어야 한다!

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

int n,m,ans=65;
int arr[8][8];

vector<pair<int,int>> cctv;
int dx[4] = {0, -1, 0, 1}; //0 == right, 1 == up, 2 == left, 3 == down
int dy[4] = {1, 0, -1, 0};

void check(int x, int y, int dir) {
    dir %= 4; // 감시 방향으로 전진
    while (true) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        x = nx;
        y = ny;
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) break;
        if(arr[nx][ny]==6) break;
        if (arr[nx][ny] !=0) continue;
        arr[nx][ny] = '#';
    }
    //return;
}
// num번째 CCTV를 회전
void bruteForce(int num) {
    if (num == cctv.size()) {
        int tmp = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 0) tmp++;
            }
        }
        ans = min(tmp, ans);
        return;
    }
    int x = cctv[num].first;
    int y = cctv[num].second;
    // 중간 정보 저장
    int store[8][8];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            store[i][j] = arr[i][j];
        }
    }
    for (int dir = 0; dir < 4; dir++) { // 0 == right, 1 == up, 2 == left, 3 == down
        //dir 1 증가하면 90도 회전
        
        if (arr[x][y] == 1) {
            check(x, y, dir); // right
        } else if (arr[x][y] == 2) {
            check(x, y, dir); // right
            check(x, y, dir + 2); // left

        } else if (arr[x][y] == 3) {
            check(x, y, dir); // right
            check(x, y, dir + 1); // up
        } else if (arr[x][y] == 4) {
            check(x, y, dir); // right
            check(x, y, dir + 1); // up
            check(x, y, dir + 2); // left

        } else if (arr[x][y] == 5) {
            check(x, y, dir); // right
            check(x, y, dir + 1); // up
            check(x, y, dir + 2); // left
            check(x, y, dir + 3); // down
        }
        bruteForce(num + 1);

        // return 받았으면 = CCTV를 한번씩 확인 했으면
        // 다시 중간 정보를 불러와서 방향 돌려보면서 확인
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = store[i][j];
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;

    for(int i=0; i<n;i++){
        for (int j=0;j<m;j++) {
            cin >> arr[i][j];
            if (arr[i][j] >= 1 && arr[i][j] <= 5) {
                cctv.push_back({ i, j });
            }
        }
    }
    bruteForce(0);
    cout << ans;
    return 0;
}