[BOJ][C++] 17135 캐슬 디펜스

문제

https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

풀이

5단계로 나누어서 구현을 했습니다. 그리 효율적인 것 같진 않은데, 더 좋은 방법이 있다면 공유해주세요!

1. 궁수 자리 배치(DFS)
2. 궁수들의 공격할 적 정하기(적이 모두 사라질 때까지 반복)
3. 공격받은 적 없애기
4. 적의 이동
5. 결괏값 확인

1. 궁수 자리 배치

  조합으로 구현했습니다.

2. 궁수들의 공격할 적 구하기

  궁수 자리 배치가 끝나고 cnt==3 조건이 만족되면, 궁수 3명이 공격할 적을 택해야합니다. 이때, 중복이 가능하기 때문에 D조건을 충족 && 최소 거리 && 최소 col 이어야 합니다.

 2-1. 궁수의 수만큼 for문을 돌려줍니다.
 2-2. 모든 적의 위치를 큐에 넣고, 큐만큼 돌려주면서 조건에 만족하는 적을 찾습니다.
 2-3. 임시 map에 0으로 표시해줍니다.
 2-4. 큐에 다시 적의 위치를 넣어줍니다.

3. 공격받은 적 없애기

 3-1. 공격 받은 적 : 공격받은 적은 임시 map에 0으로 표기되어 있습니다. 큐에 들어있는 적의 좌표 중 임시 map에 0으로 표기된 적일 경우 count를 해줍니다. 
 3-2. 공격받지 않은 적 : 임시map이 1일 경우, x+1<n 이면 (x+1, i)처럼 적이 이동한 좌표값을 큐에 넣어줍니다.
 3-3. 캐슬에 침투한 적 : x+1>=n일 경우 큐에 넣지 않습니다.

4. 적의 이동

   큐에는 살아남은 적의 이동 후 좌표가 들어있습니다. 기존 임시map을 0으로 초기화하고, 적의 좌표를 표시해줍니다.

5. 결괏값 확인

   적의 수가 0이 되면, while문을 빠져나옵니다. 이때, 3-1에서 카운팅한 값을 answer값과 비교해 max값을 표기합니다.

코드

#define MAX 987654321
#include <iostream>
#include <queue>
using namespace std;
int map[16][15];
int n, m, d;
int answer = 0;
void dfs(int index, int cnt) {
	if (cnt == 3) {
		//공격 및 적 이동
		int tmap[16][15];
		queue<pair<int, int>> q;
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j < m; j++) {
				tmap[i][j] = map[i][j];
				if (map[i][j] == 1) {
					q.push({ i,j });
				}
			}
		}
		int enamyNum = q.size();
		int res = 0;
		while (enamyNum > 0) {
			for (int i = 0; i < m; i++) {
				if (tmap[n][i] == 2) {
					//2. 공격할 적 정하기
					int min_dis = MAX;
					int min_r = MAX;
					int min_c = MAX;
					for (int j = 0; j < enamyNum; j++) {
						int x = q.front().first;
						int y = q.front().second;
						q.pop();
						int dis = abs(n - x) + abs(i - y);
						
						if (dis <= d) {
							if (dis < min_dis) {
								min_dis = dis;
								min_r = x;
								min_c = y;
							}
							else if (dis == min_dis) {
								if (y < min_c) {
									min_dis = dis;
									min_r = x;
									min_c = y;
								}
							}
						}
						q.push({ x,y });
					}
					if (min_dis!=MAX) {
						tmap[min_r][min_c] = 0;
					}
				}
			}
			int qsize = q.size();
			//3. 공격받은 적 없애기
			for (int j = 0; j < qsize; j++) {
				int x = q.front().first;
				int y = q.front().second;
				q.pop();
				if (tmap[x][y] != 0) {
					if (x + 1 < n) {
						q.push({ x + 1,y });
					}
					else enamyNum--;
				}
				else {
					enamyNum--;
					res++;
				}
			}
			//4. 적의 이동
			for (int p = 0; p < n; p++) {
				for (int q = 0; q < m; q++) {
					tmap[p][q] = 0;
				}
			}
			qsize = q.size();
			for (int j = 0; j < qsize; j++) {
				int x = q.front().first;
				int y = q.front().second;
				tmap[x][y] = 1;
				q.pop();
				q.push({ x,y });
			}
		}
		//5. 결괏값 확인
		if (res > answer) {
			answer = res;
		}
		//3.적수 maxval과 비교
		return;
	}
	if (index >= m) return;
	//선택하기
	map[n][index] = 2;
	dfs(index + 1, cnt + 1);
	map[n][index] = 0;
	//선택 안하기
	dfs(index + 1, cnt);
}
int main() {
	cin >> n >> m >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	//1. 궁수 자리 배치
	dfs(0,0);
	cout << answer << endl;
}