BOJ-17135 캐슬 디펜스

필요한 지식

1. 힙
2. 조합
3. 시뮬레이션
4. 완전탐색
5. 구현

접근

1. 조합으로 3명의 궁수를 중복되지 않게 배치한다.

2. 3명의 궁수의 적을 선택한다.

• 궁수 한명 선택
• 모든 적을 탐색 && 힙에 넣어주기
• 힙의 top은 거리가 가장 가까운, 같다면 가장 왼쪽에 있는 적이 있다.
• 그 적을 따로 저장 해 준후 모든 궁수에 대해 과정을 반복한다.

3. 선택한 적들 중 중복선택된 것은 없는지 확인 후 제거 해준다.

4. 나머지 적들을 한칸씩 옮겨준다.

힙의 top은 거리가 가장 가까운, 같다면 가장 왼쪽에 있는 적이 있게 만들기 위해 연산자 오버로딩을 사용해 주었다.

typedef struct enemy {
	int d, y, x; // 거리,y,x
	bool operator < (const enemy &tmp) const{
		if (d == tmp.d) return x > tmp.x;
		else return d > tmp.d;
	}
}enemy;

코드(C++)

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
typedef struct enemy {
	int d, y, x;
	bool operator < (const enemy &tmp) const{
		if (d == tmp.d) return x > tmp.x;
		else return d > tmp.d;
	}
}enemy;
int map[16][16], tmap[16][16], archer[3], n, m, d, ans = 0;
void copy() {
	for (int i = 0; i <= n; i++)for (int j = 0; j < m; j++)tmap[i][j] = map[i][j];
}
void move() {
	for (int i = n - 2; i >= 0; i--) {
		for (int j = 0; j < m; j++) {
			tmap[i + 1][j] = tmap[i][j];
			if (i == 0) tmap[i][j] = 0;
		}
	}
	return;
}
void go() {
	copy();
	int c = n,tans =0;
	while (c--) {
		//공격대상 지정
		vector<enemy> en;
		for (int k = 0; k < 3; k++) {
			priority_queue<enemy>pq;
			for (int i = n - 1; i >= 0; i--) {
				for (int j = 0; j < m; j++) {
					if (tmap[i][j]) {
						int dist = abs(i - n) + abs(j - archer[k]);
						if (dist <= d) pq.push(enemy{ dist,i,j });
					}
				}
			}
			if(!pq.empty()) en.push_back(pq.top());
		}
		//중복제거 및 적 제거
		for (auto it : en) {
			if (tmap[it.y][it.x]) {
				tans += 1;
				tmap[it.y][it.x] = 0;
			}
		}
		//적이동
		move();
	}
	ans = max(ans, tans);
}
void setArcher(int c,int pos) {
	if (c == 3) {
		go();
		return;
	}
	for (int i = pos; i < m; i++) {
		if (!map[n][i]) {
			map[n][i] = 1;
			archer[c] = i;
			setArcher(c + 1,i);
			map[n][i] = 0;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> d;
	for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)cin >> map[i][j];
	setArcher(0,0);
	cout << ans;
	return 0;
}