백준 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;
}