[백준 15683] 감시

# 문제

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

# 풀이

완전탐색을 통해 풀었습니다.

일단, CCTV의 종류와 위치를 따로하여서 vector에 저장했습니다.

그 후에 모든 CCTV를 돌면서 CCTV가 감시할 수 있는 모든방향을 검사하여 사각지대를 찾습니다.

CCTV의 종류마다 감시하는 구역이 중복되는 것을 눈치 채셨나요?

저는 1번, 3번,4번 카메라는 4방향 모두 돌려서 확인을 해주어야 되지만, 2번은 두번만 5번은 회전을 하지 않게끔 처리하였습니다.

dfs() 에서는 인자로 cnt를 가지고 있습니다.
이 인자는 현재 몇번째 CCTV까지 검사하였는지 나타냅니다.
그렇다면 재귀 함수의 종료 조건은 쉽게 찾아 낼 수 있겠죠?
저는 cnt > (int)cctv.size()-1 일때! 종료 하게끔 만들어 주었습니다.

88번째 라인과 91번째 라인에서 왜 'MapCopy' 함수를 호출해서 'temp' 라는 이차원 배열에 저장을 할까요?

바로 모든 CCTV의 방향을 검사하기 위해서 입니다.

만약 4×4 라는 공간에 [1,1] 과 [3,1]에 1번 카메라가 있다고 해봅시다.

[초기 Map]

0	0	0	0
0	1	0	0
0	0	0	0
0	1	0	0

1번째 카메라가 [1,1]이고 2번째 카메라가 [3,1]가 vector에 저장되게 됩니다.
모든 카메라의 방향은 위부터 시작하며 오른쪽, 아래, 왼쪽 순으로 돌아간다고 가정을 합시다.

첫번째 카메라가 위를 비춘다면 아래의 표와 같아집니다.

[1번째 Map]

0	9	0	0
0	1	0	0
0	0	0	0
0	1	0	0

그 후 두번째 카메라 또한 위를 비추면 다음과 같아집니다.

[2번째 Map]

0	9	0	0
0	1	0	0
0	9	0	0
0	1	0	0

그러고 난 뒤 모든 카메라가 비추어졌으니 사각지대를 계산을 합니다.

다음 경우의 수는 두번째 카메라가 오른쪽을 비추는 것인데 [2번째 Map]를 그대로 사용한다면 위쪽과 오른쪽을 동시에 비춘것이 되기 때문에 [1번째 Map]으로 초기화를 해주어야 됩니다.

따라서 'MapCopy' 함수는 카메라를 비추기 이전의 상황으로 돌아가기 위해 만들어 놓은 것입니다.

처음에 제출했을때 런타임 에러가 떠버렸습니다....
왜 그런지 친구랑 찾는데... 저어어기 종료 조건에서 그런거였습니다 :(

cnt == cctv.size() 는 또 잘되었습니다.
앞에 형변환을 붙이니까 지금 코드도 잘 되더군요;;;
왜그럴까요... 'size' 메소드가 unsigned long형을 반환해서 그런걸까요...?
앞으로는 저런 식으로 코딩을 하면 안되겠습니다.. 다른 변수 저장하고 해야할듯...

# 코드

#include <iostream>
#include <vector>
 
#define MAX 8
#define INF 987654321
 
using namespace std;
 
int map[MAX][MAX];
 
vector<int> cctv;
vector<pair<int, int>> cctvLocation;
 
int N,M;
int ans = INF;
 
void MapCopy(int (*a)[MAX], int (*b)[MAX]){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            a[i][j] = b[i][j];
        }
    }
}
 
void spread(int dir, int x, int y){
    //상
    if(dir == 0){
        int ny = y-1;
        if(ny < 0) return;
        if(map[ny][x] == 6) return;
        map[ny][x] = 9;
        spread(0, x, ny);
    }
    //우
    else if(dir == 1){
        int nx = x+1;
        if(nx > M-1) return;
        if(map[y][nx] == 6) return;
        map[y][nx] = 9;
        spread(1, nx, y);
    }
    //하
    else if(dir == 2){
        int ny = y+1;
        if(ny > N-1) return;
        if(map[ny][x] == 6) return;
        map[ny][x] = 9;
        spread(2, x, ny);
    }
    //좌
    else{
        int nx = x-1;
        if(nx < 0) return;
        if(map[y][nx] == 6) return;
        map[y][nx] = 9;
        spread(3, nx, y);
    }
}
 
void check(){
    int cnt = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(map[i][j] == 0){
                cnt += 1;
            }
        }
    }
    if(cnt < ans)
        ans = cnt;
}
 
void dfs(int cnt){
    if(cnt > (int)cctv.size()-1){
        //사각지대 검사
        check();
        return;
    }
    int kind = cctv[cnt];
    int x = cctvLocation[cnt].first;
    int y = cctvLocation[cnt].second;
    
    int temp[MAX][MAX];
    
    //1번 cctv는 4방향
    if(kind == 1){
        for(int i = 0; i < 4; i++){
            MapCopy(temp, map);
            spread(i, x, y);
            dfs(cnt+1);
            MapCopy(map, temp);
        }
    }
    //2번 cctv는 2방향
    else if (kind == 2){
        for(int i = 0; i < 2; i++){
            MapCopy(temp, map);
            spread(i, x, y);
            spread(i+2, x, y);
            dfs(cnt+1);
            MapCopy(map, temp);
        }
    }
    //3번 cctv는 4방향
    else if(kind == 3){
        for(int i = 0; i < 4; i++){
            MapCopy(temp, map);
            spread(i, x, y);
            spread((i+1)%4, x, y);
            dfs(cnt+1);
            MapCopy(map, temp);
        }
    }
    //4번 cctv는 4방향
    else if(kind == 4){
        for(int i = 0; i < 4; i++){
            MapCopy(temp, map);
            spread(i, x, y);
            spread((i+1)%4, x, y);
            spread((i+2)%4, x, y);
            dfs(cnt+1);
            MapCopy(map, temp);
        }
    }
    //5번 cctv는 방향 변경x
    else{
        MapCopy(temp, map);
        for(int i = 0; i < 4; i++){
            spread(i, x, y);
        }
        dfs(cnt+1);
        MapCopy(map, temp);
    }
}
 
int main(){
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            int temp;
            cin >> temp;
            map[i][j] = temp;
            if(temp != 0 && temp != 6){
                cctv.push_back(temp);
                cctvLocation.push_back(make_pair(j, i));
            }
        }
    }
    dfs(0);
    cout << ans << endl;
    return 0;
}