백준 17135 c++ "캐슬 디펜스" -[PlusUltraCode]

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

17135번: 캐슬 디펜스

[필자 사고]

 

이 문제는 구현 문제이다. 난이도가 높은 문제이다.

 

필자는 처음에 궁수의 자리를 어떻게 배치해야 할까를 고민하다 조합을 이용하여 이 부분을 해결했다.

 

그 다음 적을 죽이는 경우를 생각해보자

 

적이 사정거리 안에 있으면 죽일 수 있다. 이 부분을 우선순위 큐에 넣어 가장 가까운 적부터 죽이고 거리가 같다면 왼쪽에 더 가까운 적부터 죽이는 형식으로 코드를 작성했다. 

 

또한 궁수가 공격을 멈추었다면 적이 한칸 아래로 내려오는 과정을 반대로 생각하여 궁수의 사정거리가 1증가한다는 생각을 통해 이 부분을 해결했다.

 

마지막으로 궁수가 동일한 적을 공격할 수 있다는 조건에 주의하여 이미 공격 당한 적일경우 적을 물리친 횟수를 증가시키지  않았따.

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int N, M, D;
int ResultMax = -1;
typedef struct Node {
	int sero;
	int garo;
	int myGaro;
	int path;
};
struct cmp {
	bool operator()(Node a, Node b) {
		if (a.path == b.path) {
			return a.garo > b.garo;
		}
		return a.path > b.path;
	}
};

vector<vector<int>> Arr;
vector<bool> comVisited;

bool isInside(int mySero, int myGaro, int youSero, int youGaro,int D2) {
	int distance = abs(mySero - youSero) + abs(myGaro - youGaro);
	if (distance <= D2)return true;
	return false;
}




void Input() {
	cin >> N >> M >> D;
	Arr.resize(N+1);
	
	comVisited.resize(M, false);
	for (int i = 0; i <= N; i++) {
		Arr[i].resize(M);
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cin >> Arr[i][k];
		}
	}
}
void StartGame() {
	int Result = 0;
	vector<vector<int>> Arr2;
	vector<bool> attack; //총알
	attack.resize(M, false);
	vector<int> attackIdx; //인덱스 넣어놓ㄱ;
	  //처음 사거리
	Arr2 = Arr;
	for (int i = 0; i < M; i++) {
		if (comVisited[i] == true) {
			Arr2[N][i] = 1;
			attack[i] = true;
			attackIdx.push_back(i);
		}
	}
	priority_queue<Node, vector<Node>, cmp>pq;
	
	for (int D2 = D; D2 < D + N; D2++) {

		
		
		for (int i = 0; i < N; i++) {
			for (int k = 0; k < M; k++) {
				for (int j = 0; j < 3; j++) {
					int mySero = N;
					int myGaro = attackIdx[j];
					int youSero = i;
					int youGaro = k;
					if (Arr2[youSero][youGaro]==1&&
						isInside(mySero, myGaro, youSero, youGaro, D2)) {
						int distance = abs(mySero - youSero) + abs(myGaro - youGaro);
						pq.push({ youSero,youGaro,myGaro,distance });
						
					}
				}
			}
		}
		
		while (!pq.empty()) {
			int killGaro = pq.top().myGaro;
			int youSero = pq.top().sero;
			int youGaro = pq.top().garo;
			pq.pop();
			if (attack[killGaro] == true) {
				if (Arr2[youSero][youGaro] == 1) {
					Arr2[youSero][youGaro] = 0;
					attack[killGaro] = false;
					Result++;
				}
				else {
					attack[killGaro] = false;
				}
				
			}
		}
		for (int t = 0; t < 3; t++) {//다음번을 위한 총알장전
			attack[attackIdx[t]] = true;
		}
		for (int t = 0; t < M; t++) {
			Arr2[N - 1 -(D2-D)][t] = 0;
		}
	}

	
	if (ResultMax < Result) {
		ResultMax = Result;
	}

	
}



void Combination_Solve(int nowidx, int count) {
	if (count == 3) {
		
		StartGame();
	
		count--;
		return;
	}
	for (int i = nowidx; i < M; i++) {
		
		if (comVisited[i] == true)continue;
		comVisited[i] = true;
		Combination_Solve(i + 1, count + 1);
		comVisited[i] = false;
	}
}



int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	Combination_Solve(0,0);
	cout << ResultMax;
}