백준 17135 - 캐슬 디펜스

문제 설명

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 N x M 격자에 적들에 대한 정보가 주어졌을 때 궁수 3명을 배치해 최대한 많은 적을 처리한다면 몇 명을 처리하는지 구하면 된다.

적들은 한 턴에 한 칸씩 아래로 전진한다.

궁수가 처리할 수 있는 적은 D거리 이내에 위치해야 하고 만약 거리가 같은 적이 여러 명이라면 가장 왼쪽의 적을 처리한다.

거리 공식은 |r1-r2| + |c1-c2|이다.

 

해당 문제는 주어진 조건대로 구현하면 되는 문제이다.

구현해야 하는 부분을 정리하면 다음과 같다.

• 궁수 3명을 배치한다.
• 적들이 한 칸씩 이동한다.
• 가장 가까운(가장 왼쪽인) 적을 탐색한다.
• 적을 처리한다.

 

우선 궁수 3명을 배치하는 방법을 알아보자.

문제의 조건은 N, M이 15 이하이므로 매우 작은 경우의 수가 나온다.

따라서 3명의 궁수를 배치하는 조합을 만들어 처리하면 된다.

void DFS(vector<int>& archers, int idx)
{
    if (archers.size() == 3)
    {
        ans = max(ans, Simulate(archers));
        return;
    }

    for (int i = idx; i < M; i++)
    {
        archers.push_back(i);
        DFS(archers, i + 1);
        archers.pop_back();
    }
}

 

이제 적들이 이동하고 처리하는 부분을 구현해 보자.

적은 한 턴에 한 칸씩 움직인다.

격자의 모든 적을 찾아 한 칸씩 밑으로 내려주는 방법도 있겠지만 시간이 오래 걸릴 것이다.

따라서 처음 위치에서 몇 턴이 지났는지 기록한다면 위치를 계산할 수 있다.

이때 적들이 이동하여 성벽에 도달한다면 더 이상 공격할 수 없으므로 체크해 주고 다음 적을 이동시킨다.

for (int j = 0; j < enemies.size(); j++)
{
    if (!movable[j]) continue;
    auto [y, x] = enemies[j];
    y += moves;
    
    if (y >= N)
    {
        movable[j] = false;
        enemiesCnt--;
        continue;
    }
    ...
}

그럼 이제 배치된 궁수들에서 적들과의 거리를 계산하여 타깃을 설정하면 된다.

거리는 위에서 언급된 공식으로 간단하게 구할 수 있다.

만약 거리가 D초과라면 공격이 불가능하므로 다음 적을 탐색한다.

int dist = abs(y - N) + abs(x - archers[i]);
if (dist > D) continue;

if (dist < minDist)
{
    minDist = dist;
    minEnemy = j;
}


if (minEnemy != -1)
{
    target.insert(minEnemy);
}

거리가 가장 가까운 적을 찾았다면 바로 처리하지 않고 타깃에 추가한 후 모든 궁수의 타겟 설정이 완료되었을 때 동시에 처리해야 한다. 

그렇지 않으면 다른 궁수가 먼저 처리한 적을 제외하고 다른 타깃을 찾을 수 있기 때문에 문제의 조건에 맞지 않게 된다.

 

이때 주의할 점이 거리가 같은 적이 있으면 왼쪽의 적을 타깃으로 설정해야 하기 때문에 적들을 x좌표 기준으로 정렬을 해줘야 한다.

bool cmp(pair<int, int>& a, pair<int, int>& b)
{
    return a.second < b.second;
}

이를 반복하며 모든 적이 처리되거나 성벽에 도달하여 공격할 수 없게 되면 종료한다.

이 과정에서 처치한 적의 수의 최댓값을 갱신하면 된다.

 

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
#define MAX 987654321

using namespace std;
int N, M, D;
vector<vector<int>> grid;
vector<pair<int, int>> enemies;
int ans = 0;

int Simulate(vector<int>& archers)
{
    int moves = 0;
    int killCnt = 0;
    int enemiesCnt = enemies.size();
    vector<bool> movable(enemiesCnt, true);
    while (enemiesCnt > 0)
    {
        set<int> target;

        for (int i = 0 ; i < archers.size(); i++)
        {
            int minDist = MAX;
            int minEnemy = -1;

            for (int j = 0; j < enemies.size(); j++)
            {
                if (!movable[j]) continue;
                auto [y, x] = enemies[j];
                y += moves;
                if (y >= N)
                {
                    movable[j] = false;
                    enemiesCnt--;
                    continue;
                }

                int dist = abs(y - N) + abs(x - archers[i]);
                if (dist > D) continue;

                if (dist < minDist)
                {
                    minDist = dist;
                    minEnemy = j;
                }
            }

            if (minEnemy != -1)
            {
                target.insert(minEnemy);
            }
        }

        for (auto enemy : target)
        {
            movable[enemy] = false;
            enemiesCnt--;
            killCnt++;
        }

        moves++;
    }

    return killCnt;
}

void DFS(vector<int>& archers, int idx)
{
    if (archers.size() == 3)
    {
        ans = max(ans, Simulate(archers));
        return;
    }

    for (int i = idx; i < M; i++)
    {
        archers.push_back(i);
        DFS(archers, i + 1);
        archers.pop_back();
    }
}

bool cmp(pair<int, int>& a, pair<int, int>& b)
{
    return a.second < b.second;
}

int main()
{
    INPUT_OPTIMIZE;

    cin >> N >> M >> D;

    grid.resize(N, vector<int>(M));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> grid[i][j];
            if (grid[i][j])
            {
                enemies.push_back({ i,j });
            }
        }
    }

    sort(enemies.begin(), enemies.end(), cmp);

    vector<int> temp;
    DFS(temp, 0);

    cout << ans;
}

---