백준 17135 - 캐슬 디펜스

문제링크

• 백준 17135

문제설명

• 크기가 NxM 인 격자판에서 게임이 진행된다.(인덱스는 0번부터 시작한다고 설정)
• N번 행의 모든 칸에는 성이 있다.
• 성을 지키기 위해 궁수를 3명 배치한다. 게임은 아래와 같이 진행된다.
  • 궁수 타겟 설정
  • 궁수의 사거리 D 이하에 있는 적들 중 가장 가까우면서 가장 왼쪽에 위치한 적을 타겟으로 설정한다.
  • 모든 궁수는 동시에 타겟을 설정하며, 여러 궁수가 하나의 타겟을 설정할 수도 있다.
  • 적 공격
  • 타겟으로 설정된 적들을 공격하여 제거한다.
  • 적 이동
  • 살아남은 적들이 아래로 한 칸 이동한다. 이때 N번 행에 위치한 성에 부딪히는 경우 적은 제거된다.
• 궁수가 최대로 많이 제거할 수 있는 적의 수를 구하라

문제접근

• M명의 궁수 중 3명을 배치해야하므로 DFS를 이용해 조합을 찾는다.
• 궁수 조합마다 게임 로직을 수행한다.
  • 궁수 타겟의 경우 가까운 거리에서부터 궁수별로 타겟이 될 수 있는 후보군을 추리고, 열 값을 기준으로 오름차순 정렬해서 가장 왼쪽에 위치한 타겟을 결정한다.
    • 타겟이 없는 궁수도 있을 수 있다.
  • 적을 공격할 때 궁수끼리 중복된 타겟이 있으므로 제거되지 않은 타겟에 대해서만 공격을 하며, 제거한 타겟 수를 카운트한다.
  • 살아남은 적들이 아래로 한칸씩 이동하면서 성에 부딪히면서 사라지는 경우는 궁수가 제거한 타겟으로 카운트하지 않는다.

구현

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
using namespace std;

int N, M, D;
int board[15][15];
bool visited[15];
vector<int> archers;
vector<pair<int, int>> targets;
int ans = 0;
int numEnemy = 0;

bool cmp(pair<int, int> p1, pair<int, int>  p2) {
	return p1.second < p2.second; // 가장 왼쪽에 있는 순서대로
}

void setTarget() {
	targets.clear();
	for (int i = 0; i < archers.size(); i++) {
		vector<pair<int, int>> cand;
		for (int dist = 1; dist <= D; dist++) {
			for(int r=N-1; r>=0; r--){
				for (int c = 0; c<M; c++) {
					if (board[r][c] == 0) continue;
					int tdist = abs(N - r) + abs(archers[i] - c);
					if (dist == tdist) {
						cand.push_back(make_pair(r, c));
					}
				}
			}
			if (cand.size() > 0) break;
		}
		if (cand.size() > 0) {
			sort(cand.begin(), cand.end(), cmp);
			targets.push_back(cand[0]);
		}
	}
}

int removeEnemy() {
	int cnt = 0;
	for (int i = 0; i < targets.size(); i++) {
		int tx = targets[i].first;
		int ty = targets[i].second;
		if (board[tx][ty] == 0) continue;
		numEnemy--;
		board[tx][ty] = 0;
		cnt++;
	}

	return cnt;
}

void moveEnemy() {
	for (int r = N-1; r >= 0; r--) {
		for (int c = 0; c < M; c++) {
			if (board[r][c] == 1) {
				if (r + 1 < N) {
					board[r + 1][c] = 1;
				}
				else {
					numEnemy--;
				}
				board[r][c] = 0;
			}
		}
	}
}

int protectCattle() {
	int ret = 0;
	int cboard[15][15];
	int cNumEnemy = numEnemy;
	memcpy(cboard, board, sizeof(board));
	while (numEnemy > 0) {
		// 궁수의 목표물 설정
		setTarget();
		// 공격받은 적 게임에서 제외
		ret += removeEnemy();
		// 적 아래로 한칸 이동
		moveEnemy();
	}
	memcpy(board, cboard, sizeof(board));
	numEnemy = cNumEnemy;
	return ret;
}

void getArchers(int v) {
	if (archers.size() == 3) {
		ans = max(ans, protectCattle());
		return;
	}

	for (int i = v; i < M; i++) {
		if (visited[i]) continue;
		visited[i] = true;
		archers.push_back(i);
		getArchers(i + 1);
		archers.pop_back();
		visited[i] = false;
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d %d", &N, &M, &D);
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			scanf("%d", &board[r][c]);
			if (board[r][c] == 1) numEnemy++;
		}
	}
	memset(visited, false, sizeof(visited));
	getArchers(0);
	printf("%d\n", ans);
	return 0;
}