[백준]감시

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

15683번: 감시

처음 볼때는 아예 접근방법도 모르고 너무 복잡하다고 생각했었다..

근데 막상 좀 제대로 풀고나니까 1시간정도 걸렸었다.

가장 중요한 것은 카메라들의 방향에 대해서 완전탐색(순열)을 해주는 것이다.

각 카메라타입마다 약간의 다른방식이지만 재귀함수를 이용해 중복순열을 구현해주었다.

그리고 가장 핵심인 부분이 카메라로 감시를 하는 부분인데, 처음에는 각 카메라 마다 각 방향에 따라

구현을 해주어야 하나 너무 복잡해서 가만히 생각을 해보았다.

그냥 한 방향으로 쭉 감시하는 함수를 하나 만들어서 여러번 사용해주면 되겠다는 생각이 핵심이었던거 같다.

그리고 백업배열을 만드는건 이젠 익숙해 져서 어렵지 않았다.

 

 

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
/*
1.각각의 카메라 상태들에 대해서 완전탐색을 해야함. 카메라갯수^4 개가 있다.
2.백업 배열이 필요하다
3.5번째 카메라가 들어오면 바로 + 처리하고 신경안쓴다.
4.2번은 2방향 나머지는 4방향이다.
5.카메라가 최대한 많이봐야함. 사각지대가 최소여야함.
*/
 
struct Cam {
    int r, c;
    int type;
    Cam() {};
    Cam(int r, int c, int type) :r(r),c(c),type(type) {};
};
 
Cam c[8]; //최대 8개의 카메라
vector<int> v; //카메라 방향
int dr[] = { -1,0,1,0 }, dc[] = { 0,1,0,-1 }; //상우하좌
int N, M, C;//카메라의 개수
int map[8][8];
int back[8][8];
int ans = 1e9;
 
//정해진 방향으로 쭉 보기
void solve1(int r,int c,int dir) {
    int nr=r, nc=c;
    while (1) {
        nr += dr[dir], nc += dc[dir];
        if (nr >= 0 && nc >= 0 && nr < N && nc < M && map[nr][nc] != 6) {
            back[nr][nc] = 8;//봤다 표시
        }
        else break;
    }
}
 
void dfs(int len) {
    if (len == C) {
        
        //back에 map을 복사함
        memcpy(back, map, sizeof(back));
        
        //카메라 타입과 방향에 대해서 시뮬레이션을 돌림.
        for (int i = 0; i < C; i++) {
            int t = c[i].type, dir = v[i];
            int rr = c[i].r, cc = c[i].c;
            
            if (t == 1) solve1(rr, cc, dir);
            else if (t == 2) {
                if (dir == 0) { solve1(rr, cc, 0); solve1(rr, cc, 2); }
                else if (dir == 1) { solve1(rr, cc, 1); solve1(rr, cc, 3); }
            }
            else if (t == 3) {
                if (dir == 0) { solve1(rr, cc, 0); solve1(rr, cc, 1);}
                else if (dir == 1) { solve1(rr, cc, 1); solve1(rr, cc, 2); }
                else if (dir == 2) { solve1(rr, cc, 2); solve1(rr, cc, 3); }
                else if (dir == 3) { solve1(rr, cc, 0); solve1(rr, cc, 3); }
            }
            else if (t == 4) {
                if (dir == 0) { solve1(rr, cc, 0); solve1(rr, cc, 1); solve1(rr, cc, 3); }
                else if (dir == 1) { solve1(rr, cc, 0); solve1(rr, cc, 1); solve1(rr, cc, 2); }
                else if (dir == 2) { solve1(rr, cc, 1); solve1(rr, cc, 2); solve1(rr, cc, 3); }
                else if (dir == 3) { solve1(rr, cc, 0); solve1(rr, cc, 2); solve1(rr, cc, 3); }
            }
            else if (t == 5) { solve1(rr, cc, 0); solve1(rr, cc, 2); solve1(rr, cc, 1); solve1(rr, cc, 3); }
        }
 
        //최소값 체크
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (back[i][j] == 0) cnt++;
            }
        }
        if (ans >= cnt) ans = cnt;
        
        return;
    }
 
    //방향에 대한 순열을 만들어준다... 카메라 타입에 따라 약간 다르다
    //시작이 계속 0이고, 방문체크도 안하므로 순열이다.
    //방문한것 체크해서 안해주면 중복X순열이다
    //시작을 하나씩 늘려가며 해주면 조합이다.
 
    if (c[len].type == 1 || c[len].type == 3 || c[len].type == 4) {
        for (int i = 0; i < 4; i++) {
            v.push_back(i);
            dfs(len + 1);
            v.pop_back();
        }
    }
    else if (c[len].type == 2) {
        for (int i = 0; i < 2; i++) {
            v.push_back(i); //0이면 상하 , 1이면 좌우
            dfs(len + 1);
            v.pop_back();
        }
    }
    else if (c[len].type == 5) {
        v.push_back(1); //1이면 상하좌우
        dfs(len + 1);
        v.pop_back();
    }
}
 
int main()
{    
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j] != 0 && map[i][j] != 6) { c[C] = Cam(i, j, map[i][j]); C++; }
        }
    }
    
    dfs(0);
    printf("%d\n", ans);
    
    return 0;
}