[백준 17135] 캐슬 디펜스 (C++)

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

문제

---

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

 

입력

---

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

 

출력

---

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

 

제한

---

• 3 ≤ N, M ≤ 15
• 1 ≤ D ≤ 10

문제 풀이

---

구현 문제.

 

궁수 3명의 위치를 정한 후 궁수들이 해당 위치에 위치해 있을 때 몇 명의 적을 제거할 수 있는지 시뮬레이션해본다.

하나의 조합을 구했다면, 궁수가 공격 거리 제한 D 범위 내에서 공격할 수 있는 적들을 공격한다. 게임판에서 해당 적들을 모두 제거한다. 그 후 남은 적들을 한 칸 앞으로 이동시킨다. 이를 적이 게임판에서 모두 제외될 때까지 반복한다.

 

따라서 다음과 같은 순서로 시뮬레이션되고, 각 부분에 대해 구현해주면 된다.

1. 궁수 3명의 위치 조합 하나를 구한다.
2. 해당 위치 조합에 대해 각 궁수들이 현재 턴에 제거하는 적들을 구한다.
3. 보드 판에서 현재 턴에 제거되는 적들을 제거한다.
4. 남은 적들을 한 칸 앞으로 이동시킨다.
5. 게임판에서 모든 적들이 제거될 때까지 2-4를 반복한다.
6. 모든 궁수 3명의 위치 조합에 대해 1-5를 반복한다.

백트래킹을 통해 가능한 궁수 3명의 위치 조합을 모두 구할 수 있다.

 

각 궁수에 대해 궁수가 위치한 위치를 기반으로 적들과의 거리를 구해, 가장 가까운 적의 위치를 구해 현재 턴에 공격받는 적의 위치를 저장하는  set에 저장해둔다. 궁수들이 동시에 공격하므로 여러 궁수가 한 적을 동시에 공격할 수 있기 때문에 set에 저장해두는 것이다.

모든 궁수가 공격하는 적의 위치를 구했다면 set의 처음부터 끝까지 탐색하며 해당 위치의 격자판의 상태를 0으로 바꾸고, 적을 제거하였으므로 count를 1 증가시킨다.

 

그 다음 성에서 가까운 순서대로 적을 이동시키고, 모든 적들이 보드판에서 제거되었는지 확인해준다. 

 

아래는 코드.

백트래킹 함수 backTracking()을 통해 depth가 3일 때(=궁수 3명의 위치 조합이 정해질 때), 한 조합에서 제거하는 적의 수를 카운트하는 변수와 보드판을 초기로 되돌리고 해당 조합에 대해 시뮬레이션 하는 함수 simulate()를 호출한다.

simulate()함수는 모든 적들이 제거될 때까지 궁수가 공격하고 해당 적들이 제거되는 attack()함수와 남은 적들이 이동하는 move()함수를 호출한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
using namespace std;
int** original;
int** arr;
int N, M, D;
int* positions = new int[3];
bool* isAllocated;
int maxEliminateEnemies;
int currentSimulationEnemies;

void attack()
{
	set<pair<int, int>> attackedEnemies;
	for (int archer = 0; archer < 3; archer++)
	{
		pair<int, int> archerPos = pair(N, positions[archer]);
		pair<int, int> attackedPos = pair(N+1, M+1);
		int minDistance = 11;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				int currentDistance = abs(archerPos.first - i) + abs(archerPos.second - j);
				if (arr[i][j] == 1 && currentDistance < minDistance && currentDistance <= D)
				{
					minDistance = currentDistance;
					attackedPos = pair(i, j);
				}
				else if (arr[i][j] == 1 && currentDistance == minDistance&& currentDistance <= D)
				{
					if (j < attackedPos.second)
					{
						attackedPos = pair(i, j);
					}
				}
			}
		}
		if (attackedPos != pair(N + 1, M + 1))
		{
			attackedEnemies.insert(attackedPos);
		}
	}
	for (set<pair<int, int>>::iterator it = attackedEnemies.begin(); it != attackedEnemies.end(); it++)
	{
		pair<int, int> attackedPos = *it;
		arr[attackedPos.first][attackedPos.second] = 0;
		currentSimulationEnemies++;
	}
}

void move()
{
	for (int i = N - 2; i >= 0; i--)
	{
		for (int j = 0; j < M; j++)
		{
			arr[i + 1][j] = arr[i][j];
			arr[i][j] = 0;
		}
	}
}

bool checkFinished()
{
	bool isFinished = true;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (arr[i][j] == 1)
			{
				isFinished = false;
			}
		}
	}
	return isFinished;
}

void simulate()
{
	while (true)
	{
		attack();
		move();
		if (checkFinished() == true)
		{
			break;
		}
	}
}

void copy()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			arr[i][j] = original[i][j];
		}
	}
}

void backTracking(int depth, int index)
{
	if (depth == 3)
	{
		currentSimulationEnemies = 0;
		copy();
		simulate();
		maxEliminateEnemies = max(maxEliminateEnemies, currentSimulationEnemies);
	}
	else
	{
		for (int i = index; i < M; i++)
		{
			if (isAllocated[i] == false)
			{
				positions[depth] = i;
				isAllocated[i] = true;
				backTracking(depth + 1, i+1);
				isAllocated[i] = false;
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M >> D;
	original = new int* [N];
	arr = new int*[N];
	isAllocated = new bool[M];
	for (int i = 0; i < M; i++)
	{
		isAllocated[i] = false;
	}
	for (int i = 0; i < N; i++)
	{
		original[i] = new int[M];
		arr[i] = new int[M];
		for (int j = 0; j < M; j++)
		{
			cin >> original[i][j];
		}
	}
	backTracking(0, 0);
	cout << maxEliminateEnemies << "\n";
	return 0;
}