[백준 17135] 캐슬 디펜스

분류 

분류, dfs

요구사항

적들이 0행~n-1행으로 이동할때, 궁수를 적절히 배치하여 처치할 수 있는 적들의 최대 수 구하기

풀이

전체적 문제의 흐름은 아래와 같다

1. dfs로 궁수 위치 정해주기

2. 적에서 궁수까지 거리 구하기

3. 제일 가까우면서 왼쪽에 있는 적 없애기

4. 적 이동

2~4번 반복

 

3번은 sort를 이용하여 처리하였다. 잡을 경우, map[r][c]가 1이면 0으로 바꾸어주고 cnt를 1증가 시켰다.

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string.h> 
#include <math.h>

using namespace std;

struct go {
	int dist;
	int c;
	int r;
};
int n, m, d;
int map[17][17];
int visit[16];
int ans = 0;
bool check() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 1)
				return false;
		}
	}
	return true;
}
bool cmp(go a, go b) {
	if (a.dist < b.dist) {
		return true;
	}
	else if (a.dist == b.dist) {
		if (a.c < b.c) return true;
	}
	return false;
}

void Get_ans(int arr[]) {
	int cnt = 0;
	vector<go> v[16];
	int pos[16];
	for (int i = 0; i < m; i++) {
		if (visit[i] == 1) {
			pos[cnt++] = i;
		}
	}
	cnt = 0;
	while (true) {
		if (check()) {
			break;
		}
		//모든 궁수로 부터 적까지 거리 구하기
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 1) {
					for (int k = 0; k <3; k++) {
						int dist = abs(i - n) + abs(j - pos[k]);
						if (dist <= d) {
							v[pos[k]].push_back({ dist,j,i });
						}
					}
				}
			}
		}
		//제일 가까우면서 왼쪽에 있는 적 찾기
		for (int i = 0; i <3; i++) {
			if (!v[pos[i]].empty()) {
				sort(v[pos[i]].begin(), v[pos[i]].end(), cmp);
				int x = v[pos[i]][0].r;
				int y = v[pos[i]][0].c;
				if (map[x][y] == 1) {
					cnt++;
					map[x][y] = 0;
				}
				v[pos[i]].clear();
			}
		}
		//적들 밑으로 한 칸 이동하기
		for (int i = n - 1; i >= 0; i--) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 1) {
					if (i == n - 1)
						map[i][j] = 0;
					else {
						map[i][j] = 0;
						map[i + 1][j] = 1;
					}
				}
			}
		}

	}
	ans = max(ans, cnt);
}
void solve(int cnt, int now) {

	if (now == m) {
		if (cnt == 3) {
			int mapc[17][17];
			memcpy(mapc, map, sizeof(map));
			Get_ans(visit);
			memcpy(map, mapc, sizeof(map));
		}
		return;
	}
	visit[now] = 1;
	solve(cnt + 1, now + 1);
	visit[now] = 0;
	solve(cnt, now + 1);

}

int main() {
	scanf("%d%d%d", &n, &m, &d);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	solve(0, 0);
	cout << ans << endl;
}