(c++)백준 17145번: 캐슬 디펜스

www.acmicpc.net/problem/17135

[풀이]

문제에 나온 게임 순서대로 구현하였다.

1. 궁수 3명 배치: dfs를 이용하여 궁수 위치의 조합을 만들어 각 조합마다 게임을 진행하였다.

2. 적의 존재 여부 확인 및 적의 위치 저장(적이 존재하지 않으면 게임 끝)

3. 궁수마다 가장 가까운 적 찾아서 공격: 궁수와 가장 가까운 적을 찾고 그 적이 아직 공격받지 않았다면 공격할 수 있는 적의 수로 카운트 해주고 제외한다.

4. 적 아래로 한 칸 이동: 맵의 범위 넘어가면 제외 ※첫번째 줄부터 아래로 내려가면서 이동시키면 맵이 의도한 것과 다른 모양이 될 수 있으므로 마지막 줄부터 위로 올라가면서 이동시켜야 함!!

 

#include <iostream>
#include <vector>
#include <cstring>//memset
#include <algorithm>//max
#include <cstdlib>//abs
using namespace std;

struct Pos {
	int x, y;
};

int N, M, D;
int Map[15][15];
int cMap[15][15];
bool check[15];//궁수 자리
bool killed[15][15];//해당 적이 죽었는지
int Max = -1;
vector<Pos>Archer;//궁수 위치
vector<Pos>Enemy;//적의 위치

void init() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cMap[i][j] = Map[i][j];
		}
	}
}

bool checkEnemy() {
	Enemy.clear();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (cMap[i][j] == 1)
				Enemy.push_back({ i,j });
		}
	}
	if (Enemy.size() == 0)
		return false;
	else return true;
}

void Move() {
	for (int i = N-1; i >=0; i--) {
		for (int j = 0; j < M; j++) {
			if (cMap[i][j] == 1) {
				cMap[i][j] = 0;
				if (i + 1 != N) {
					cMap[i + 1][j] = 1;
				}
			}
		}
	}
}

void Game() {
	init();
	int kill_cnt = 0;
	while (checkEnemy()) {//적 존재 여부와 위치 저장
		memset(killed, false, sizeof(killed));
		//궁수마다 가장 가까운 적 찾아서 공격
		for (int i = 0; i < 3; i++) {
			int dist = 0;
			int Min = 987654321;
			int ex, ey;
			bool exist = false;
			//가장 가까운 적 찾기
			for (int j = 0; j < Enemy.size(); j++) {
				dist = abs(N - Enemy[j].x) + abs(Archer[i].y - Enemy[j].y);
				if (dist > D)
					continue;
				exist = true;
				if (Min > dist) {
					Min = dist;
					ex = Enemy[j].x;
					ey = Enemy[j].y;
				}
				else if (Min == dist) {
					if (Enemy[j].y < ey) {
						ex = Enemy[j].x;
						ey = Enemy[j].y;
					}
				}
			}
			if (exist == false)
				continue;
			//가장 가까운 적 공격
			if (killed[ex][ey] == false) {
				killed[ex][ey] = true;
				cMap[ex][ey] = 0;
				kill_cnt++;
			}
		}
		Move();
	}
	Max = max(Max, kill_cnt);
}

//궁수 위치 정하고 게임 시작
void dfs(int y, int cnt) {
	if (cnt == 3) {
		Game();
		return;
	}

	for (int i = y; i < M; i++) {
		if (check[i] == true)
			continue;
		check[i] = true;
		Archer.push_back({ N,i });
		dfs(i, cnt + 1);
		Archer.pop_back();
		check[i] = false;
	}
}

void solution() {
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> Map[i][j];
		}
	}
	dfs(0, 0);
	cout << Max << '\n';
}

int main() {
	solution();
	return 0;
}