15683번

15683번 - 감시

상반기 대기업 SW 역량 평가로 나왔는데, 풀었던 문제였다. 

브루트포스로 하나씩 문제를 쪼개면 풀 수 있는 문제였다. 나는 실제 시험장에서 fill_map을 makeMap 함수안에 각각 구현해서 코드가 굉장

히 더러웠었던 기억이 난다ㅋㅋㅋ

일단 모든 CCTV를 90도로 돌려가면서, 최소의 사각지대를 만들어야 한다. 그래서 재귀함수로 모든 케이스를 탐색하도록 구현했다.

근데 일단 조금이라도 속도를 줄이고자, 90도로 돌렸을 때 나올 수 있는 가짓수를 dir_num 배열에 넣어줬다.

CCTV 1번은 4방향이 모두 다르다, 하지만 CCTV 2번 같은 경우에는 2가지 경우만 존재하고, 5번 같은 경우에는 1가지 경우만 존재한다.

그리고 이를 통해서 getMIN 함수에서 for문으로 몇가지 방법으로 돌릴지 정해서 for문을 구성했다.

makeMap 함수에서는 if 문을 통해서 노가다로 각 방향에 맞게 케이스를 나누어 주었다. 이것도 배열로 막 하려고 했는데 머리가 아파서 그냥

각 케이스를 if문을 이용해서 넣어주었다.

그리고 중요한 점은 add_val 값을 100으로 했는데, 처음에 단순하게 1로 해주고 -1로 원상복귀해주는 방식으로 했더니

CCTV 1번 번호도 map 에서 1이기 때문에 약간 겹치는 것 같아서 아예 큰 숫자인 100, -100으로 브루트 포스를 진행했다.

정답을 구하는 ans 변수는 사각지대의 최대 갯수는 n,m 의 최대 갯수가 8개 이므로 8*8인 64개를 넘지 않을 것이라 생각하여 좀 더 큰 수인 

100으로 초기화를 시켜서 문제를 풀었다.

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
int dir_num[6] = { 0,4,2,4,4,1 };
int n, m, ans;
int map[8][8];
vector<pair<int, int>> cctv;
 
//실질적으로 맵을 채우는 함수.
void fill_map(int x,int y,int dx,int dy,int add_val)
{
    int nx = x + dx;
    int ny = y + dy;
 
    //벽과 CCTV 이외의 지점에서 add_val 만큼 더해줌.
    while (nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] != 6)
    {
        if (map[nx][ny] == 0 || map[nx][ny]>=100)
        {
            map[nx][ny] += add_val;
        }
 
        nx +=dx;
        ny += dy;
    }
}
 
//맵을 어느 방향으로 채울 것인가 정하는 함수
void makeMap(int x,int y, int number, int d,int add_val)
{
    if (number == 1) {
        if (d == 0) {
            fill_map(x, y, 0, 1,add_val);
        }
        if (d == 1) {
            fill_map(x, y, 1, 0, add_val);
        }
        if (d == 2) {
            fill_map(x, y, 0, -1, add_val);
        }
        if (d == 3) {
            fill_map(x, y, -1, 0, add_val);
        }
    }
    
    if (number == 2) {
        if (d == 0) {
            fill_map(x, y, 0, 1, add_val);
            fill_map(x, y, 0, -1, add_val);
        }
        if (d == 1) {
            fill_map(x, y, 1, 0, add_val);
            fill_map(x, y, -1, 0, add_val);
        }
    }
 
    if (number == 3) {
        if (d == 0) {
            fill_map(x, y, -1, 0, add_val);
            fill_map(x, y, 0, 1, add_val);
        }
        if (d == 1) {
            fill_map(x, y, -1, 0, add_val);
            fill_map(x, y, 0, -1, add_val);
        }
        if (d == 2) {
            fill_map(x, y, 1, 0, add_val);
            fill_map(x, y, 0, 1, add_val);
        }
        if (d == 3) {
            fill_map(x, y, 1, 0, add_val);
            fill_map(x, y, 0, -1, add_val);
        }
    }
 
    if (number == 4) {
        if (d == 0) {
            fill_map(x, y, -1, 0, add_val);
            fill_map(x, y, 0, 1, add_val);
            fill_map(x, y, 0, -1, add_val);
        }
        if (d == 1) {
            fill_map(x, y, 0, -1, add_val);
            fill_map(x, y, 1, 0, add_val);
            fill_map(x, y, -1, 0, add_val);
        }
        if (d == 2) {
            fill_map(x, y, 0, 1, add_val);
            fill_map(x, y, 0, -1, add_val);
            fill_map(x, y, 1, 0, add_val);
        }
        if (d == 3) {
            fill_map(x, y, 0, 1, add_val);
            fill_map(x, y, 1, 0, add_val);
            fill_map(x, y, -1, 0, add_val);
        }
    }
 
    if (number == 5) {
        fill_map(x, y, 0, 1, add_val);
        fill_map(x, y, 0, -1, add_val);
        fill_map(x, y, 1, 0, add_val);
        fill_map(x, y, -1, 0, add_val);
    }
}
 
//사각지대를 구하는 함수
int getSize()
{
    int ret = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (map[i][j] == 0)
                ret++;
 
 
    return ret;
}
void getMIN(int cctv_num)
{
    //cctv 갯수만큼 구했을 때 최소값 구하기
    if (cctv_num == cctv.size())
    {
        int cur_size = getSize();
        if (cur_size < ans)
            ans = cur_size;
 
        return;
    }
 
 
    int x = cctv[cctv_num].first;
    int y = cctv[cctv_num].second;
    int number = map[x][y];
 
    //각 CCTV 마다 90도 회전할 수 있는 경우만큼 for문
    for (int i = 0; i < dir_num[number]; i++)
    {
        makeMap(x, y, number, i, 100);
        getMIN(cctv_num + 1);
        makeMap(x, y, number, i, -100);
 
 
    }
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
    ans = 100;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
 
            //CCTV에 해당하는 좌표 vector 에 추가
            if (map[i][j] >= 1 && map[i][j] <= 5)
                cctv.push_back({ i,j });
        }
    
    getMIN(0);
 
    cout << ans << endl;
 
 
    return 0;
}