백준 17135번: 캐슬 디펜스

[문제 링크]

17135번: 캐슬 디펜스

---

재밌으면서도 골치아팠던 그래프 & 시뮬레이션 문제였다.

우선 궁수를 3명 배치하는 조합의 경우 3중 for문을 이용하여 간단하게 구현할 수 있다.

그 다음, 궁수가 공격할 대상을 정하는 것을 구현해야 하는데 조건은 다음과 같다.

 

1. 궁수는 동시에 공격한다. --> 같은 적을 여러명의 궁수가 공격하게 될 수 있다.

2. 사거리 내 적이 여러명 있는 경우 가장 가까이 있는 적을 공격한다.

3. 같은 사거리에 있는 적의 경우 가장 왼쪽에 있는 적을 공격한다.

 

여러명의 궁수가 같은 적을 공격하는 경우 킬포인트가 중복으로 누적되는 것을 방지하기 위해 이미 죽은 적은 '2'로 마킹하여 공격은 하되, 킬포인트는 올라가지 않도록 구현하였다.

---

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int N, M, D;
int board[15][15];

class Archer {
private:
	int y;
	int x;
	int distance;
	int kill;
public:
	Archer(int _x) : y(N), distance(D), kill(0) {
		x = _x;
	}

	void searchEnemy() {
		for (int d = 1; d <= distance; d++) {
			int i = 1;
			while (i <= d) {
				int yPos = y - i;
				int xPos = x - d + i;

				if (yPos >= 0 && xPos >= 0) {
					int& enemy = board[yPos][xPos];
					if (enemy != 0) {
						attack(enemy);
						return;
					}
				}

				i++;
			}

			i = d - 1;

			while (i >= 1) {
				int yPos = y - i;
				int xPos = x + d - i;

				if (yPos >= 0 && xPos < M) {
					int& enemy = board[yPos][xPos];
					if (enemy != 0) {
						attack(enemy);
						return;
					}
				}

				i--;
			}
		}
	}

	void attack(int& enemy) {
		if (enemy == 1) {
			enemy = 2;
			kill++;
		}
	}

	int getKillCount() {
		return kill;
	}
};

void moveEnemy() {
	int temp[15][15];
	memcpy(temp, board, sizeof(temp));

	for (int y = N-1; y >= 0; y--) {
		for (int x = 0; x < M; x++) {
			int state = temp[y][x];
			if (state != 0) {
				if (state == 1) {
					int nextY = y + 1;
					if (nextY < N)
						board[nextY][x] = 1;
				}
				board[y][x] = 0;
			}
		}
	}
}

bool isEndGame() {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (board[i][j] == 1)
				return false;

	return true;
}

int maximumKillCount() {
	int result = 0;

	for (int i = 0; i < M; i++) {
		for (int j = i + 1; j < M; j++) {
			for (int k = j + 1; k < M; k++) {
				int killCount = 0;

				Archer* archer1 = new Archer(i);
				Archer* archer2 = new Archer(j);
				Archer* archer3 = new Archer(k);

				int backup[15][15];
				memcpy(backup, board, sizeof(backup));

				while (!isEndGame()) {
					archer1->searchEnemy();
					archer2->searchEnemy();
					archer3->searchEnemy();

					moveEnemy();
				}

				killCount += archer1->getKillCount();
				killCount += archer2->getKillCount();
				killCount += archer3->getKillCount();

				result = max(result, killCount);

				memcpy(board, backup, sizeof(board));

				delete archer1;
				delete archer2;
				delete archer3;
			}
		}
	}

	return result;
}

int main(void) {
	cin >> N >> M >> D;
	
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> board[i][j];

	cout << maximumKillCount() << endl;

	return 0;
}