[ 백준 15683 ] 감시 (C++)

 

백준의 감시(15683) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 맵의 크기와 맵의 현재 상태가 주어진다. 맵에는 빈공간이 존재하며, 1~5번까지의 CCTV가 있다.

- CCTV는 번호마다 감시할 수 있는 감시방향의 갯수와 방향이 다르다.

- 또한 CCTV들은 90도 방향으로 회전시킬 수 있으며, 대각선은 감시할 수 없다.

- 이 때, CCTV가 감시할 수 없는 사각지대의 영역이 최소가 될 때, 사각지대의 크기를 구하면 된다.

[ 문제풀이 ]

1. 이 문제는 CCTV가 어느 방향으로 감시할 때, 사각지대의 최소값을 구해야 하므로 모든 경우를 다해봐야 하는 완전탐색

   문제이다.

2. 먼저, 맵을 입력 받을 때, 본인은 CCTV가 있는 곳의 위치들은 Vector에 넣어주었는데, 4개의 값을 Vector에 넣어주었다.

   [(x,y) , (카메라번호, -1)] 이렇게 4개의 값을 넣어주었다.

   여기서 가장 뒤에 있는 -1은 카메라의 방향을 나타내기 위해서 사용하였으며, 초기값은 -1로 설정해주었다.

3. 이후 모든 CCTV의 방향을 설정해 주어야 하는데, 약간 생각을 해봐야할 부분이 있다.

   CCTV가 1번이 하나 있고, 2번이 하나 있다고 가정해보자. 1번은 동/서/남/북 중 한 방향만 감시가 가능하고

   2번은 동서 / 남북 이렇게 2방향으로 감시가 가능하다.(CCTV는 회전이 가능하므로)

   그렇다면, 1번이 동쪽을 보고 2번이 동서 쪽을 감시할 때, 1번이 동쪽을 보고 2번이 남북쪽을 감시할떄 등등등...

   이렇게 모든 경우를 다 고려해 주어야 한다.

4. 3)번에서 말한 방향을 설정해주기 위해서 (함수 : Set_CCTV_Direction(int Cnt)) 먼저 CCTV의 총 갯수를 판단하였다.

   CCTV의 총 갯수는 입력받을 때 넣어준 Vector의 Size로 설정해주었고, Vector의 가장 마지막 값인 -1의 값을

   0, 1, 2, 3(동 서 남 북)으로 바꿔가면서 값을 넣어주었다. 코드를 보면서 구체적으로 설명을 하자면....

  

   < 방향을 설정해주는 함수 >

   위의 함수처럼 구현을 하였는데, 보면 계속해서 재귀가 호출되는 것을 볼 수 있다. 함수가 호출되는 과정을 설명해보면

   CCTV가 3개이고, CCTV의 번호가 1,3,5 번호이라고 가정해보겠다.

   가장 먼저 Cnt로 0의 값을 호출하는데, 이 경우에 V[0].second.second = 0 으로 바뀌게 된다.

   이후, Cnt의 값을 증가시켜서 1이 되면, V[1].second.second = 0 이 되고, 이후 V[2].second.second = 0이 될 것이다.

   모든 CCTV의 방향이 설정되었으므로 조건문에 걸리게 되어, 계산하는 과정으로 들어가게된다.

   계산이 끝났다면, 돌아오는 곳은 V[2].second.second = 1 이 부분으로 돌아올 것이다.(재귀를 깊게 생각해보면 됨 !)

   이렇게 되면, 지금 계산한 영역은 (0번카메라 = 동쪽, 1번카메라 = 동쪽, 2번카메라 = 동쪽) 일 때가 되고,

   그 다음 계산할 때에는 (0번카메라 = 동쪽, 1번카메라 = 동쪽, 2번카메라 = 서쪽) 이런 식으로 계산이 될 것이다.

   재귀의 호출과정만 잘 알고 있다면 위의 코드가 모든 방향에 대해서 적용이 된다는 것을 알 것이다.

5. 카메라의 방향에 따른 감시 영역을 체크할 때, 나는 감시 당하는 영역을 맵에서 -1로 바꿔주었다.

   물론, 이러한 과정을 위해서 맵을 복사하는 과정이 있고, 원본의 맵을 유지할 수 있어야 한다.

   이후, 맵에서 0의 갯수를 Count하여 최소값을 갱신해 주는 방향으로 구현하였다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 8
using namespace std;
 
int N, M, CCTV_Num, Answer;
int MAP[MAX][MAX];
int C_MAP[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
vector<pair<pair<int, int>, pair<int, int>>> V;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    Answer = 99999999;
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            if (1 <= MAP[i][j] && MAP[i][j] <= 5)
            {
                V.push_back(make_pair(make_pair(i, j), make_pair(MAP[i][j], -1)));
            }
        }
    }
    CCTV_Num = V.size();     
}
 
void Copy_MAP()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            C_MAP[i][j] = MAP[i][j];
        }
    }
}
 
void Right(int x, int y)
{
    for (int i = y+1; i < M; i++)
    {
        if (C_MAP[x][i] == 6) break;
        if (1 <= C_MAP[x][i] && C_MAP[x][i] <= 5) continue;
        
        C_MAP[x][i] = -1;
    }
}
 
void Left(int x, int y)
{
    for (int i = y - 1; i >= 0; i--)
    {
        if (C_MAP[x][i] == 6) break;
        if (1 <= C_MAP[x][i] && C_MAP[x][i] <= 5) continue;
 
        C_MAP[x][i] = -1;
    }
}
 
void Down(int x, int y)
{
    for (int i = x + 1; i < N; i++)
    {
        if (C_MAP[i][y] == 6) break;
        if (1 <= C_MAP[i][y] && C_MAP[i][y] <= 5) continue;
 
        C_MAP[i][y] = -1;
    }
}
 
void Up(int x, int y)
{
    for (int i = x - 1; i >= 0; i--)
    {
        if (C_MAP[i][y] == 6) break;
        if (1 <= C_MAP[i][y] && C_MAP[i][y] <= 5) continue;
 
        C_MAP[i][y] = -1;
    }
}
 
void Check_CCTV_Area()
{
    Copy_MAP();
    for (int i = 0; i < V.size(); i++)
    {
        if (V[i].second.first == 1)
        {
            if (V[i].second.second == 0) Right(V[i].first.first, V[i].first.second);
            else if (V[i].second.second == 1) Left(V[i].first.first, V[i].first.second);
            else if (V[i].second.second == 2) Down(V[i].first.first, V[i].first.second);
            else if (V[i].second.second == 3) Up(V[i].first.first, V[i].first.second);
        }
        else if (V[i].second.first == 2)
        {
            if (V[i].second.second == 0 || V[i].second.second == 1)
            {
                Right(V[i].first.first, V[i].first.second);
                Left(V[i].first.first, V[i].first.second);
            }
            else if (V[i].second.second == 2 || V[i].second.second == 3)
            {
                Up(V[i].first.first, V[i].first.second);
                Down(V[i].first.first, V[i].first.second);
            }
        }
        else if (V[i].second.first == 3)
        {
            if (V[i].second.second == 0)
            {
                Up(V[i].first.first, V[i].first.second);
                Right(V[i].first.first, V[i].first.second);
            }
            else if (V[i].second.second == 1)
            {
                Right(V[i].first.first, V[i].first.second);
                Down(V[i].first.first, V[i].first.second);
            }
            else if (V[i].second.second == 2)
            {
                Down(V[i].first.first, V[i].first.second);
                Left(V[i].first.first, V[i].first.second);
            }
            else if (V[i].second.second == 3)
            {
                Left(V[i].first.first, V[i].first.second);
                Up(V[i].first.first, V[i].first.second);
            }
        }
        else if (V[i].second.first == 4)
        {
            if (V[i].second.second == 0)
            {
                Left(V[i].first.first, V[i].first.second);
                Up(V[i].first.first, V[i].first.second);
                Right(V[i].first.first, V[i].first.second);
            }
            else if (V[i].second.second == 1)
            {
                Up(V[i].first.first, V[i].first.second);
                Right(V[i].first.first, V[i].first.second);
                Down(V[i].first.first, V[i].first.second);
            }
            else if (V[i].second.second == 2)
            {
                Right(V[i].first.first, V[i].first.second);
                Down(V[i].first.first, V[i].first.second);
                Left(V[i].first.first, V[i].first.second);
            }
            else if (V[i].second.second == 3)
            {
                Down(V[i].first.first, V[i].first.second);
                Left(V[i].first.first, V[i].first.second);
                Up(V[i].first.first, V[i].first.second);
            }
        }
        else if (V[i].second.first == 5)
        {
            Right(V[i].first.first, V[i].first.second);
            Left(V[i].first.first, V[i].first.second);
            Up(V[i].first.first, V[i].first.second);
            Down(V[i].first.first, V[i].first.second);
        }
    }
}
 
int NumOfSecretArea()
{
    int Sum = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (C_MAP[i][j] == 0) Sum++;
        }
    }
    return Sum;
}
 
void Set_CCTV_Direction(int Cnt)
{
    if (Cnt == CCTV_Num)
    {
        Check_CCTV_Area();
        Answer = Min(Answer, NumOfSecretArea());
        return;
    }
 
    V[Cnt].second.second = 0;
    Set_CCTV_Direction(Cnt + 1);
 
    V[Cnt].second.second = 1;
    Set_CCTV_Direction(Cnt + 1);
 
    V[Cnt].second.second = 2;
    Set_CCTV_Direction(Cnt + 1);
 
    V[Cnt].second.second = 3;
    Set_CCTV_Direction(Cnt + 1);
}
 
void Solution()
{
    Set_CCTV_Direction(0);
}
 
void Solve()
{
    Input();
    Solution();
    
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}