[ 백준 17135 ] 캐슬 디펜스 (C++)

백준의 캐슬 디펜스(17135) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는 궁수를 적절히 배치함으로써 적군을 최대한 많이 물리 칠 수 있도록 구현하는 문제이다.

    궁수는 총 3명이며, 궁수는 맵의 가장 마지막줄 + 1줄에 위치한다고 생각하면 된다.

    그렇다면 순차적으로 무엇을 왜 구현해야 하는지부터 알아보면서 시작해보자.

   

    1. 조합 구현하기

    - 본인이 생각한 1단계 구현은 조합을 구현하는 것이다. 왜 조합을 구현해야할까 ?? 바로 궁수의 자리 떄문이다.

       이 문제는 궁수 3명이 각각 어디에 위치하냐에 따라서 결과값이 달라지고, 그 결과값 중 최댓값을 구해야 하는

       문제이기 때문이다.

       그럼 왜 순열이 아니고 왜 조합인지도 알아보자.

       5칸 짜리 성에 3명의 궁수가 자리잡는다고 생각해보자. 각 칸은 0번칸 ~ 4번칸으로 이루어져있다고 생각할 때,

       궁수 3명을 1번, 2번, 3번으로 이름붙인다고 생각했을 때,

       1번궁수 = 성의 0번칸, 2번궁수 = 성의 1번칸, 3번궁수 = 성의 2번칸에 위치하는 경우와

       1번궁수 = 성의 2번칸, 2번궁수 = 성의 0번칸, 3번궁수 = 성의 1번칸에 위치하는 경우를 생각해보자.

       과연 결과값이 다를까?? 아니다. 결과는 같을 것이다. 각 궁수별로 사거리가 다른것도 아니고, 모든 궁수는

       동일한 사거리를 가지고 있기 때문에 결과는 같게 나올 것이다.

       즉, "순서가 상관이 없는 조합"을 구현하면 궁수를 배치시킬 수 있는 모든 경우에 배치하면서 구현을 진행할

       수 있을 것이다.

       혹시나 ! 아직 조합을 구현하는 법을 잘 모른다면 아래의 글을 읽고 오도록 하자.

       [ 조합 구현하는 법 알아보기 ! (Click) ]

 

       즉, 우리는 M개 중에 3개를 뽑는 조합을 구현함으로써, 궁수 3명이 "총 M개의 성 위에서 서로다른 3개의 성

       위에 위치" 하게 만들 수 있을 것이다.

       M개 중에 뽑는 이유는, 맵의 가로 길이가 M이기 때문이다. 맵의 가로 길이가 M이라면, 그 문제에서

       성의 총 길이도 M칸이 될 것이기 때문이다.

   2. 조합에 의해서 구현된 궁수들의 위치에서 적들을 죽이기

   - 지금까지 우리는 궁수들을 조합을 통해서 배치해 주었다. 그렇다면, 이제는 궁수들이 적을 죽이는 과정을

      구현해야 할 것이다. 그렇다면 궁수가 어떤 적을 죽이는지 조건을 한번 더 확인하자.

     "사정거리 내에 있는 적들 중에서, 가장 가까운 적을 죽인다. 만약, 가장 가까운 적이 여러명이라면, 가장 왼쪽에

      있는 적을 죽인다."

      본인은 이 부분을 위해서, Vector를 하나 사용해 주었다. Vector가 관리하는 자료형은 본인이 임의적으로 만든

      구조체이다. 구조체가 관리하는 자료들로는 { x좌표(int), y좌표, 거리(int) } 이렇게 3개의 변수들을 관리해 주었다.

      이 후, 현재 궁수의 좌표와 적의 거리를 계산해서 사정거리 내에 존재하는 적이라면 Vector에 넣어주었다.

      (사용한 Vector의 본문에서 이름 = vector<Enemy_Info> Kill_Enemy_Temp)

      (본문에 보면 Vector<pair<int, int> V라는 Vector가 있는데, 여기서는 이 Vector를 말하는게 아닙니다 !)

      그렇다면, 사정거리내에 있는 모든 적들을 다 Vector에 넣은 후에 Vector의 size는 얼마가 될까??

      당연히 경우에 따라 다를 것이다.

      지금부터 Vector의 Size에 따른 구현을 알아보자.

      먼저, Vector의 Size가 0이라는 것은 무엇을 의미할까 ?? 해당 궁수가 죽일 수 있는 적이 없음을 의미한다.

      그렇다면 Vector의 Size가 1이라는 것은 무엇을 의미할까?? 해당 궁수가 죽일 수 있는 적이 1명이라는 것을

      의미한다. 이 경우에는, 해당 궁수는 무조건 그 적을 죽일 수 밖에 없다. 그 1명인 적군이 가장 가까운 적군이기

      때문이다.

      그렇다면 Vector의 Size가 2 이상이라는 것은 무엇을 의미할까??

      해당 궁수가 죽일 수 있는 적군이 2명 이상이라는 것을 의미한다. 그렇다면, 이 경우에는 어떤 적을 죽여야 할까?

      바로, 위의 조건에 맞게, 거리가 가장 가까운 적을 1차적으로 그게 여러명이라면 가장 왼쪽에 있는 적을 죽여야

      한다. 본인은 이 부분을 위해서, Vector의 Size가 2이상일 경우에는 이 Vector를 Sorting을 시켜 주었다.

      Sorting의 기준은, 1차적으로 거리가 더 가까운 놈들이 앞으로 오게, 2차적으로는 더 왼쪽에 있는 놈들이 앞으로

      오도록 정렬해 주었다.

      이렇게 정렬했을 때, Vector의 0번째에 있는 데이터는 어떤 데이터일까??

      바로, 거리가 가장 가까우면서도 가장 왼쪽에 있는 적군이 0번째에 데이터로 존재하게 될 것이다.

      즉, 이 경우에는 Sorting 시킨 후, 0번째 데이터에 존재하는 적군을 죽여버리면 조건에 맞는 적군을 죽이게 되는 것

      이다. 가장 가까운지 판단은 구조체의 거리를 저장하는 변수로, 더 왼쪽에 있는지는 구조체의 y좌표를 저장하는

      변수로 판단해 주었다.

      이제, 적군을 죽였으면 이거를 어떻게 표시해줘야 할까 ?? 죽은 적군은 아마 맵에서 1이 아닌 0으로 표현될 것이다.

      그렇다면, 이제 값을 0으로만 바꿔주면 되는데 여기서 중요한 것은 "3명의 궁수가 모두 쏜 후에, 0으로 바꿔줘야 한

      다" 라는 것이다. 왜 그럴까??

      한 명의 적군은 여러명의 궁수에게 동시에 공격받을 수 있기 때문이다.

      즉, 1번궁수도 x라는 적을 쏠 수도 있고, 2번 궁수도 x라는 적을 쏠 수도 있고, 3번 궁수도 x라는 적을 쏠 수 있는

      경우가 발생한다. 즉, 1번 궁수가 x를 쏴서 x가 죽었다고 판단 하고, 2번 궁수에게 x에게 쏠 기회조차 안주게 된다면

      이는 문제의 조건에 위배되는 것이고 정답이 제대로 나오지 않게 될 것이다.

     

      따라서, 본인은 이를 위해서 pair<int, int> Arrow_Target[3] 이라는 pair형 자료를 하나 선언해 주었다.

      여기에는 무엇이 저장될까? 바로 각 궁수들이 쏜 적군들의 (x, y)좌표가 pair로 저장되게 된다.

      모든 궁수들이 적을 죽일 때 까지는 죽인 적군들을 pair로만 저장해주고, 실제로 0으로 바꿔서 죽였다고 표시는

      하지 않는다. 모든 궁수들이 다 화살을 쏜 후에, pair에 저장된 값을 통해서 맵에서 0으로 바꿔주는 계산을 하였다.

      또한, 0으로 바꿔준다는 것은 적군을 한명 죽였다는 의미인데, 만약 3명이 동일한 1명의 적군을 죽였다면, 이 때는

      3명이 Count되는 것이 아닌 1명이 Count되야 하므로 이를 Visit[][] 2차원 배열을 통해서 설정해 주었다.

   3. 적군 움직이기

   - 이제 적을 죽였으니, 살아남은 적군들은 성쪽으로 한칸씩 내려오게 된다. 이를 위해서 살아 남은 적군들을 한 칸씩

      밑으로 움직여 주면 된다. 이 부분은 어렵지 않으니 코드를 참고 하도록 하자.

      이 부분에서 주의할 점으로는, 가장 윗줄에서부터 아랫줄로 탐색하면서 적군들을 내리면 이상하게 맵이 바뀌는

      경우가 존재하니, 가장 아랫줄에서부터 윗줄로 올라가는 순서로 적군들을 내려주도록 하자.

   4. 언제까지 이걸 해야되?

   - 이제부터는 2번 3번을 계속해서 반복해야 되는데, 언제까지 해야 될까? 바로 적군이 한 명도 존재하지 않을 때 까지

      해줘야 한다. 본인은 이부분을 구현하기 위해서, 2번 3번 과정을 하는 부분을 무한루프로 묶어주었고

      무한루프를 종료하는 조건함수를 하나 걸어주었다.

      그 조건함수는 바로 맵에 적군들이 존재하는지 존재하지 않는지를 판단하는 함수이다.

      또한, 이 함수에서 적군이 존재한다면, 그 적군들의 좌표를 저장해 주었다.

      갑자기 이게 무슨 소리일까??

      2번 과정을 생각해보면, 궁수가 적군들과의 거리를 계산해서 Vector에 넣어주고 뭐 누구를 죽이고 어떻게 저장하고

      이런 말만 있었지, 적군들의 좌표를 어떻게 저장해 놓았는지에 대해서는 아무런 말도 없었다.

      물론, 적군들의 좌표를 미리 저장해 놓을 필요 없이, 모든 맵을 돌면서 '1'이 나올 때마다 계산을 해줘도 무관하지만

      이러면 필요없는 반복문이 너무 많이 발생할 것 같아서 본인은 미리 Vector에 저장해 주었다.

      여기서 사용한 함수는 본문에서 Vector<pair<int,int>> V 이다.

      다시 한번 정리해보자. 우리는 적군들이 없을 때 까지 적군을 죽이고, 적군을 밑으로 움직이는 과정을 반복해 줘야

      한다. 이 때, "적군들이 없을 때" 라는 조건문을 만들기 위해서 함수를 하나 만들었고, 이 함수에서는 적군이 있다면

      그 적군들을 모두 V라는 Vector에 넣어주고, 만약 적군이 한 명도 없다면 true를 반환함으로써 종료하게 해 주었다.

      아래 코드를 보면서 이해해보자.

bool All_Kill()                    // 모든 적군을 죽였는지 판단하는 함수
{
    bool Flag = true;             // Flag라는 Return 값 선언
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)    // 모든 맵을 모두 돌아보면서
        {
            if (C_MAP[i][j] == 1)    // 만약 적군이 존재한다면
            {
                Flag = false;        // Flag의 값을 false로 바꿔주고
                V.push_back(make_pair(i, j));    // 적군의 위치를 V에 push
            }
        }
    }
    return Flag;    // 적군이 한명도 없었다면 true를, 그게 아니라면 false를 반환
}

       또한, 우리가 여기서 주의해줘야 할 것은 원본 MAP을 그대로 사용하면 안된다는 것이다.

       우리가 지금까지 한 것은 어떤 경우인지 잘 생각해 주어야 한다.

       우리는 궁수 3명이 성 M칸 중에서, 특정 3칸에 자리잡고 그 이후에 일어난 일들을 지금까지 쭉 한 것이다.

       아마 이 다음 단계는 궁수 3명이 그 다음 특정 3칸에 자리잡고 이 일을 반복하는 것일 것이다.

       그렇기 때문에, 원본의 맵에서 적군을 움직여버리고 적군을 없애버리고 하면 결국 그 다음 단계에서는

       제대로 작동될리가 없다. 따라서 MAP을 복사해 주어야 한다는 것을 생각해주자.

       또한, 적군을 죽이고, 적군을 움직이는 무한루프 안에서, 루프가 한 번 돌때마다 V Vector와 Visit배열은

       초기화를 시켜줘야 한다. 왜 그럴까??

       V Vector의 역할이 무엇인지 생각해보자. V Vector는 "현재 살아있는 적군들의 좌표를 저장하는 벡터" 이다.

       루프가 한 번 돌면, 분명히 죽은 적군들이 존재하게 될 것이고, V에는 다시 새로운 값들이 들어가줘야 하기 때문

       이다. Visit배열의 역할은, 여러 궁수의 화살을 동시에 맞은 적군이 존재할 때, 그 적군을 중복해서 Count해주는

       것을 막기 위한 배열인데, 루프가 돌면서 그 자리에 새로운 적군이 와서 죽을 수도 있기 때문에 이 부분을

       확실하게 계산해 주기 위해서 Visit배열 또한 초기화 해주어야 한다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
 
#define endl "\n"
#define MAX 15
using namespace std;
 
typedef struct
{
    int x;
    int y;
    int Dist;
}Enemy_Info;
 
int N, M, D, Answer, Temp_Answer;
int MAP[MAX][MAX];
int C_MAP[MAX][MAX];
bool Visit[MAX][MAX];
bool Select[MAX];
vector<pair<int, int>> V;
vector<int> Pos;
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N >> M >> D;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Copy_MAP()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            C_MAP[i][j] = MAP[i][j];
        }
    }
}
 
bool All_Kill()
{
    bool Flag = true;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (C_MAP[i][j] == 1)
            {
                Flag = false;
                V.push_back(make_pair(i, j));
            }
        }
    }
    return Flag;
}
 
int Dist(int x, int y, int xx, int yy)
{
    return abs(x - xx) + abs(y - yy);
}
 
bool Standard(Enemy_Info A, Enemy_Info B)
{
    if (A.Dist <= B.Dist)
    {
        if (A.Dist == B.Dist)
        {
            if (A.y < B.y)
            {
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
}
 
void Shot()
{
    pair<int, int> Arrow_Target[3];
 
    for (int i = 0; i < Pos.size(); i++)
    {
        int x = N;
        int y = Pos[i];
        vector<Enemy_Info> Kill_Enemy_Temp;
 
        for (int j = 0; j < V.size(); j++)
        {
            int xx = V[j].first;
            int yy = V[j].second;
 
            int Distance = Dist(x, y, xx, yy);
            if (Distance <= D)
            {
                Enemy_Info Temp;
                Temp.x = xx;
                Temp.y = yy;
                Temp.Dist = Distance;
                Kill_Enemy_Temp.push_back(Temp);
            }
        }
 
        int Kill_Num = Kill_Enemy_Temp.size();
        if (Kill_Num > 1)
        {
            sort(Kill_Enemy_Temp.begin(), Kill_Enemy_Temp.end(), Standard);
            Arrow_Target[i].first = Kill_Enemy_Temp[0].x;
            Arrow_Target[i].second = Kill_Enemy_Temp[0].y;
        }
        else if (Kill_Num == 1)
        {
            Arrow_Target[i].first = Kill_Enemy_Temp[0].x;
            Arrow_Target[i].second = Kill_Enemy_Temp[0].y;
        }
        else
        {
            Arrow_Target[i].first = -1;
            Arrow_Target[i].second = -1;
        }
    }
 
    for (int i = 0; i < 3; i++)
    {
        int x = Arrow_Target[i].first;
        int y = Arrow_Target[i].second;
        
        if (x == -1 && y == -1) continue;
        if (Visit[x][y] == false)
        {
            Visit[x][y] = true;
            C_MAP[x][y] = 0;
            Temp_Answer++;
        }
    }
}
 
void Move_Enemy()
{
    for (int i = V.size() - 1; i >= 0; i--)
    {
        int x = V[i].first;
        int y = V[i].second;
 
        if (C_MAP[x][y] == 0) continue;
        if (x == N - 1)
        {
            C_MAP[x][y] = 0;
        }
        else
        {
            C_MAP[x][y] = 0;
            C_MAP[x + 1][y] = 1;
        }
    }
}
 
void Print()
{
    cout << "#######################################################" << endl;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cout << C_MAP[i][j] << " ";
        }
        cout << endl;
    }
    cout << "#######################################################" << endl;
}
 
void Kill_The_Enemy()
{
    Copy_MAP();
    while (1)
    {
        V.clear();
        memset(Visit, false, sizeof(Visit));
 
        if (All_Kill() == true) break;
        Shot();
        Move_Enemy();
    }
}
 
void Select_Pos(int Idx, int Cnt)
{
    if (Cnt == 3)
    {
        Temp_Answer = 0;
        Kill_The_Enemy();
        Answer = Bigger(Answer, Temp_Answer);
        return;
    }
 
    for (int i = Idx; i < M; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        Pos.push_back(i);
        Select_Pos(i, Cnt + 1);
        Pos.pop_back();
        Select[i] = false;
    }
}
 
void Solution()
{
    Select_Pos(0, 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;
}