구현 문제이다. 아래 알고리즘이 복잡해 보이지만 크게 3가지 단계의 반복으로 볼 수 있다.
- 궁수 3명을 배치한다.
- 궁수를 기준으로 D 거리 안의 적을 왼쪽부터 공격한다.
- 적이 한칸 앞으로 온다. 이 때 N-1 위치에 있는 적은 사라진다.
궁수 3명을 배치하는 과정은 dfs()
함수로 나타냈다. 배치가 끝나면 kill()
과 goEnemy()
함수를 반복하며 count
를 더해 제거한 적 수를 저장해주었다. kill()
함수에서는 bfs를 사용하여 D
거리 안에 있는 적을 제거하였다. 여기서 주의할 점은 궁수는 같은 적을 공격할 수 있다는 점이다. 그래서 적을 발견한 시점에서 바로 제거하지 않고 zero
벡터에 저장해 준 후 모든 궁수의 범위 내의 적을 구하면 그 후에 반복문을 돌며 제거해주면서 카운트해주었다. goEnemy()
함수에서는 만약 모든 적이 제거되었다면 false
를 리턴하여 반복문을 끝내고, 적이 존재하면 한 칸 앞으로 이동시켜준다. 이를 반복하며 최대로 제거한 적의 수를 구해 출력해주었다.
생각보다 오래 걸린 문제였다. 중간 중간 오타와 잘못된 문제 이해로 인해 시간 낭비가 많았다. 주의하자.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
int N, M, D, res = 0;
vector<int> v;
int A[15][15];
int B[15][15];
int kill() {
int count = 0;
int dy[3] = { 0, -1, 0 };
int dx[3] = { -1,0,1 };
vector<pair<int, int>> zero;
for (int k = 0; k < 3; k++) {
queue<pair<pair<int, int>, int>> q;
bool check[15][15];
memset(check, 0, sizeof(check));
q.push({ { N - 1,v[k] },1 });
check[N - 1][v[k]] = true;
while (!q.empty()) {
int y = q.front().first.first;
int x = q.front().first.second;
int c = q.front().second;
q.pop();
if (c > D) break;
if (B[y][x] == 1) {
zero.push_back({ y,x });
break;
}
for (int i = 0; i < 3; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
if (check[ny][nx]) continue;
check[ny][nx] = true;
q.push({ { ny,nx }, c + 1 });
}
}
}
for (int i = 0; i < zero.size(); i++) {
int y = zero[i].first;
int x = zero[i].second;
if (B[y][x] == 1) {
B[y][x] = 0;
count++;
}
}
return count;
}
bool goEnemy() {
bool tf = false;
for (int i = N - 1; i >= 0; i--) {
for (int j = 0; j < M; j++) {
if (B[i][j] == 1) {
B[i][j] = 0;
if (i != N - 1) {
B[i + 1][j] = 1;
}
tf = true;
}
}
}
return tf;
}
void dfs(int depth) {
if (v.size() == 3) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
B[i][j] = A[i][j];
}
}
int count = 0;
while (1) {
count += kill();
if (!goEnemy()) break;
}
res = max(res, count);
return;
}
for (int i = depth; i < M; i++) {
v.push_back(i);
dfs(depth + 1);
v.pop_back();
}
}
void solution(){
dfs(0);
cout << res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> M >> D;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> A[i][j];
}
}
solution();
return 0;
}