[BOJ] - 17135. 캐슬 디펜스

[URL]

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

17135번: 캐슬 디펜스

​

[풀이 과정]

​

* 재귀DFS + 시뮬레이션

(주의 사항)

- 각각의 (a1, a2, a3)에 대한 enemy벡터 초기화

- target 조건 1, 2

​

​

1. map[][] == 1인 곳 (x,y)좌표 데이터 enemy 벡터로 저장

​

2. go()를 통해 가능한 궁수의 위치 3곳 구한다. (재귀 DFS) --> (a1, a2, a3)

​

3. 각각의 (a1, a2, a3)에 대해 캐슬디펜스 시작

​

4. a1, a2, a3 각각의 target을 구한다. --> (t1, t2, t3)

< target의 조건 ! >

* 거리가 D이하 이면서 가장 가까운 거리의 적

* 여럿일 경우, 가장 왼쪽의 적 -----------> 이 조건을 처음에 빼먹어서 헤맸다.

​

5. enemy벡터를 검사하며 t1, t2, t3인 경우, 벡터에서 삭제 후, sum++

​

6. (a1, a2, a3) 에 대해 나온 (sum: 제거 할 수 있는 적의 수) cand[]배열에 저장

​

7. cand[] 중 가장 큰 수 출력!!

​

​

[소스 코드]

 

#include <stdio.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N, M, D;
int map[20][20];
bool check[20] = { 0, };
 
int arrow[3];
 
int cand[9999];
int candCnt;
 
struct info {
    int x;
    int y;
};
 
vector <info> enemy;
vector <info> enemyCopy;
 
void init() {
    candCnt = 0;
 
    scanf("%d %d %d", &N, &M, &D);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            scanf("%d", &map[i][j]);
 
            if (map[i][j] == 1)
            {
                info temp;
                temp.x = i;
                temp.y = j;
 
                enemy.push_back(temp);
            }
        }
    }
}
 
bool cmp(info a, info b) {
    return a.y < b.y;
}
 
info findNearTarget(int A)
{
    int tempDist;
    vector <info> nearCand;
 
    int nearDist = 987654321;
 
    for (int i = 0; i < enemyCopy.size(); i++)
    {
        tempDist = abs(N - enemyCopy[i].x) + abs(A - enemyCopy[i].y);
 
        if (tempDist <= D)
        {
            if (nearDist >= tempDist)
            {
                nearDist = tempDist;
            }
        }
    }
 
    for (int i = 0; i < enemyCopy.size(); i++)
    {
        tempDist = abs(N - enemyCopy[i].x) + abs(A - enemyCopy[i].y);
 
        if (tempDist == nearDist)
        {
            info temp;
            temp.x = enemyCopy[i].x;
            temp.y = enemyCopy[i].y;
 
            nearCand.push_back(temp);
        }
    }
 
    sort(nearCand.begin(), nearCand.end(), cmp);
 
    info nearEnemy;
 
    if (nearCand.size() == 0)
    {
        nearEnemy.x = -99;
        nearEnemy.y = -99;
    }
    else
    {
        nearEnemy.x = nearCand.front().x;
        nearEnemy.y = nearCand.front().y;
    }
 
    return nearEnemy;
}
 
int goCalc()
{
    int sum = 0;
 
    while (enemyCopy.size() != 0)
    {
        // 삭제 할 타겟 구해온다!
        info target1 = findNearTarget(arrow[0]);
        info target2 = findNearTarget(arrow[1]);
        info target3 = findNearTarget(arrow[2]);
 
        // 타겟 삭제
        if (target1.x != -99)
        {
            for (int i = 0; i < enemyCopy.size();)
            {
                if (target1.x == enemyCopy[i].x && target1.y == enemyCopy[i].y)
                {
                    enemyCopy.erase(enemyCopy.begin() + i);
                    sum++;
                }
                else
                    i++;
            }
        }
 
        if (target2.x != -99)
        {
            for (int i = 0; i < enemyCopy.size();)
            {
                if (target2.x == enemyCopy[i].x && target2.y == enemyCopy[i].y)
                {
                    enemyCopy.erase(enemyCopy.begin() + i);
                    sum++;
                }
                else
                    i++;
            }
        }
 
        if (target3.x != -99)
        {
            for (int i = 0; i < enemyCopy.size();)
            {
                if (target3.x == enemyCopy[i].x && target3.y == enemyCopy[i].y)
                {
                    enemyCopy.erase(enemyCopy.begin() + i);
                    sum++;
                }
                else
                    i++;
            }
        }
 
        // 적군 한칸씩 내리기
        for (int i = 0; i < enemyCopy.size();)
        {
            enemyCopy[i].x = enemyCopy[i].x + 1;
 
            if (enemyCopy[i].x == N)
                enemyCopy.erase(enemyCopy.begin() + i);
 
            else
                i++;
        }
    }
 
    return sum;
}
 
void go(int cnt)
{
    if (cnt == 3)
    {
        for (int i = 0; i < enemy.size(); i++)
        {
            info temp;
            temp.x = enemy[i].x;
            temp.y = enemy[i].y;
 
            enemyCopy.push_back(temp);
        }
 
        cand[candCnt] = goCalc();
        candCnt++;
        return;
    }
 
    for (int i = arrow[cnt - 1]; i < M; i++)
    {
        if (check[i] == false)
        {
            check[i] = true;
            arrow[cnt] = i;
 
            cnt++;
 
            go(cnt);
 
            cnt--;
            check[i] = false;
        }
    }
}
 
int main()
{
    init();
    go(0);
    int Max = 0;
    for (int i = 0; i < candCnt; i++)
    {
        if (cand[i] >= Max)
        {
            Max = cand[i];
        }
    }
    printf("%d\n", Max);
 
    return 0;
}