백준 15683 / 감시

문제를 읽었을 때, 어떻게 해결해야할지 단계가 나눠져야 한다.

내가 해결한 방법은 

1.  cctv의 번호와 방향을 pair로 집어넣는다. 이떄 dfs를 사용하여 어떤 방향을 비출지에 대한 모든 경우의 수를 담는다.

                   1번 : 동 1, 서 2, 남 3, 북 4

   2번 : 동서 1, 남북 2

   3번 : 동북 1, 서북 2, 서남 3, 동남 4

   4번 : 북x 1, 동x 2, 서x 3, 동x 4    

  5번 : 동서남북 1

2. 집어넣은 cctv를 하나씩 꺼내어, 번호와 방향을 확인한다.

3. cctv의 번호와 방향에 따라 동,서,남,북 한 방향씩 빛(cctv가 쏘는??)을 비춘다.

4. map이 0이면서 빛이 비추어지지 않은 칸을 세어 최소값과 비교한다.

   cctv가 위치한 칸과 벽은 사각지대에 포함이 되지 않는다.

cctv의 형태가 다양해 코드가 좀 길다. 줄일 수 있을까..

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<memory.h>
 
using namespace std;
 
int map[8][8];
bool check[8][8];
 
pair<int, int> tmpdir[9];
vector<pair<int, int>>cctv;
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
int n, m;
int minn = 2000000;
int ans = 0;
 
void light(int x, int y, int dir) {
 
    bool end = false;
    int a = 1;
    while (end == false) {
 
        int nx = x + a * dx[dir - 1];
        int ny = y + a * dy[dir - 1];
 
        if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
            if (map[nx][ny] != 6) {
                check[nx][ny] = true;
                a++;
            }
            else {
                end = true;
            }
        }
        else {
            end = true;
        }
 
    }
 
    return;
}
 
void go() {
 
    for (int i = 0; i < cctv.size(); i++) {
        int x = cctv[i].first;
        int y = cctv[i].second;
        
        int num = map[x][y];
        int dir = tmpdir[i].second;
 
        check[x][y] = true;
 
        /* 1번 : 동 1, 서 2, 남 3, 북 4
           2번 : 동서 1, 남북 2
           3번 : 동북 1, 서북 2, 서남 3, 동남 4
           4번 : 북x 1, 동x 2, 서x 3, 동x 4
           5번 : 동서남북 1
        */
 
        if (num == 1) {
            light(x, y, dir);
        }
        if (num == 2) {
            if (dir == 1) {
                light(x, y, 1);
                light(x, y, 2);
            }
            if (dir == 2) {
                light(x, y, 3);
                light(x, y, 4);
            }
        }
        if (num == 3) {
            if (dir == 1) {
                light(x, y, 1);
                light(x, y, 4);
            }
            if (dir == 2) {
                light(x, y, 2);
                light(x, y, 4);
            }
            if (dir == 3) {
                light(x, y, 2);
                light(x, y, 3);
            }
            if (dir == 4) {
                light(x, y, 1);
                light(x, y, 3);
            }
        }
        if (num == 4) {
            if (dir == 1) {
                light(x, y, 1);
                light(x, y, 2);
                light(x, y, 3);
            }
            if (dir == 2) {
                light(x, y, 1);
                light(x, y, 2);
                light(x, y, 4);
            }
            if (dir == 3) {
                light(x, y, 1);
                light(x, y, 3);
                light(x, y, 4);
            }
            if (dir == 4) {
                light(x, y, 2);
                light(x, y, 3);
                light(x, y, 4);
            }
        }
        if (num == 5) {
            light(x, y, 1);
            light(x, y, 2);
            light(x, y, 3);
            light(x, y, 4);
        }
    }
}
 
void makedir(int idx) {
 
 
    if (idx == cctv.size()) {
        memset(check, false, sizeof(check));
        ans = 0;
 
        go();
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (check[i][j] == false && map[i][j]==0) {
                    ans++;
                }
            }
        }
        
        if (minn > ans) {
            minn = ans;
        }
        return;
    }
 
    int x = cctv[idx].first;
    int y = cctv[idx].second;
    int num = map[x][y];
 
    if (num == 1) {
        for (int i = 1; i < 5; i++) {
            tmpdir[idx] = { 1,i };
            makedir(idx + 1);
        }
    }
    if (num == 2) {
        for (int i = 1; i < 3; i++) {
            tmpdir[idx] = { 2,i };
            makedir(idx + 1);
            
        }
    }
    if (num == 3) {
        for (int i = 1; i < 5; i++) {
            tmpdir[idx] = { 3,i };
            makedir(idx + 1);
        }
    }
    if (num == 4) {
        for (int i = 1; i < 5; i++) {
            tmpdir[idx] = { 4,i };
            makedir(idx + 1);
        }
    }
    if (num == 5) {
        tmpdir[idx] = { 5,1 };
        makedir(idx + 1);
    }
 
    return;
}
int main() {
    //freopen("Text.txt", "r", stdin);
    cin >> n >> m;
 
    minn = 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) {
                cctv.push_back({ i,j });
            }
            if (map[i][j] == 6) {
                check[i][j] = true;
            }
        }
    }
 
    makedir(0);
 
    cout << minn;
}