시뮬레이션 + 백트래킹 문제이다.
1차적으로 궁수 3명을 N+1 번째 행에 3명을 조합의 경우의 수로 세워둔다. 그 다음 2차적으로 시간을 N까지 증가시키면서 적들을 아래 칸으로 한칸씩 움직이도록 한다. 3차적으로 한 칸씩 움직인 적들 중 각 궁수에게 가장 가까운, 거리가 같다면 제일 왼쪽에 있는 놈을 찾는 O(NlogN) 로직을 짜준다. 그 후 하나하나 죽이면서 죽는 놈들을 세어주면 된다.
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <string.h>
#include <math.h>
#define MAX_NUM 1000000009
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
int n, m, d;
int arr[17][17];
int check[16][16];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
vector<pii> am;
int maxn = 0;
pii arc_pos;
int cur_time;
bool compare(pii a, pii b) {
int ta = abs(a.first + cur_time - arc_pos.first) + abs(a.second - arc_pos.second);
int tb = abs(b.first + cur_time - arc_pos.first) + abs(b.second - arc_pos.second);
if (ta == tb) {
return a.second < b.second;
}
else {
return ta < tb;
}
}
int getAnmy(vector<pii> &arc) {
int res = 0;
int am_check[17][17] = { 0, };
int checked[17][17] = { 0, };
// 시간 [0, n)
for (int t = 0; t < n; t++) {
vector<pii> shoted;
// 적 위치 -> 각 궁수들은 자신과 가장 가까운 놈을 찾아야함
for (int j = 0; j < arc.size(); j++) {
int ax = arc[j].first;
int ay = arc[j].second;
arc_pos = { ax, ay };
cur_time = t;
sort(am.begin(), am.end(), compare);
for (auto pos : am) {
int sx = pos.first;
int sy = pos.second;
if (sx + t > n) continue;
if (abs(sx + t - ax) + abs(sy - ay) > d) break;
if (checked[sx][sy]) continue;
if (am_check[sx][sy] == 0)
shoted.push_back({ sx, sy });
am_check[sx][sy] = 1;
break;
}
}
for (int j = 0; j < shoted.size(); j++) {
int tx = shoted[j].first;
int ty = shoted[j].second;
checked[tx][ty] = 1;
res += 1;
}
}
return res;
}
void bt(int num, int cnt, vector<pii> &arc) {
int x = n+1, y = num;
if (cnt == 3) {
int res = getAnmy(arc);
maxn = max(res, maxn);
return;
}
if (num > m) return;
arc.push_back({ x, y });
bt(num + 1, cnt + 1, arc);
arc.pop_back();
bt(num + 1, cnt, arc);
}
int main() {
scanf("%d %d %d", &n, &m, &d);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &arr[i][j]);
if (arr[i][j])
am.push_back({ i,j });
}
}
vector<pii> arc;
bt(1, 0, arc);
printf("%d\n", maxn);
return 0;
}17135번: 캐슬 디펜스
첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.
www.acmicpc.net
'책장 > 알고리즘' 카테고리의 다른 글
| [백준-23295] 스터디 시간 정하기 1 (0) | 2021.11.05 |
|---|---|
| [백준-1939] 중량제한 (0) | 2021.10.21 |
| [백준-3020] 개똥벌레 (0) | 2021.10.01 |
| [백준-14391] 종이조각 (0) | 2021.10.01 |
https://www.acmicpc.net/problem/17135