[BOJ]백준 17135번: 캐슬 디펜스

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

17135번: 캐슬 디펜스

삼성 SW역량테스트 A형에 나왔던 문제이다.

전형적인 브루트포스 문제!!

 

이 문제를 풀 때 고민했던게 궁수의 위치 조합은 DFS로 금방 되겠는데 적의 위치 탐색은....?

첫번째 구현할 때는 한 칸씩 이동할 때 마다 BFS로 탐색을 한 뒤 1. 거리, 2. x좌표 순으로 정렬을 했었다

그그런데 왠지 시간낭비같아서 그냥 아예 처음에

궁수별로 적의 모든 좌표에 대해 거리와 x좌표 순으로 정렬하고, 시간이 지날 때 마다 궁수의 사거리를 1씩 늘려줬다

그러면 매 탐색마다 갱신하지 않아도 되니까

 

전체적인 로직은

 

1. 궁수의 위치 조합을 구한다(3명밖에 안 되기 때문에 그냥 3중반복문 돌렸다)

2. 3명의 궁수 벡터에 모든 적의 초기 좌표와 거리를 넣고 정렬

3. 만약 적이 처치되지 않았고(전 턴에!!), y좌표가 이미 지나지 않았으며, 거리가 닿는다면

   배열에 넣어준다.

4. 3명의 궁수가 처리할 적이 정해지면 배열에 체크하고 숫자를 카운팅

 

로직은 맞았는데 계속 맞왜틀이어서 정말 엄청 뜯어고친 결과 메인함수의 3중 반복문에서 경계를 m이 아닌 n으로 써줬더라.... 하

n과 m은 헷갈리니까 앞으로는 row와 col로 쓰기로 했다

밑은 나의 코드

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
struct point { int d, x, y; };
int n, m, d, ans, map[30][30];
bool e[16][16];
vector<point> v[3], del; 
vector<point>::iterator it;
bool cmp(point a, point b) {
	if (a.d == b.d)return a.x < b.x;
	return a.d < b.d;
}
int func(int* arr) {
	int max = 0;
	memset(e, false, sizeof(e));

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			for (int k = 0; k < 3; k++) {
				if (map[i][j]) {
					v[k].push_back({ abs(j - arr[k]) + abs(n - i) ,j,i });
				}
			}
	for (int k = 0; k < 3; k++)
		sort(v[k].begin(), v[k].end(), cmp);

	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0, k; j < 3; j++) {
			for (it = v[j].begin(); it != v[j].end(); it++)
				if (!e[(*it).y][(*it).x] && (*it).y <= i && (*it).d <= d + n - i - 1)
					break;

			if (it != v[j].end())
				del.push_back({ 0,(*it).x,(*it).y });
		}

		for (int j = 0; j < del.size(); j++) {
			if (e[del[j].y][del[j].x])continue;
			max++;
			e[del[j].y][del[j].x] = true;
		}
		del.clear();
	}
	for (int k = 0; k < 3; k++)
		v[k].clear();

	return max;

}
int main() {
	//freopen("input.txt", "r", stdin);
	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]);

	for (int i = 0; i < m - 2; i++)
		for (int j = i + 1; j < m - 1; j++)
			for (int k = j + 1; k < m; k++) {
				int ac[3], t;
				ac[0] = i, ac[1] = j, ac[2] = k;
				t = func(ac);
				ans = t > ans ? t : ans;
			}
	printf("%d", ans);
	return 0;
}