[BOJ] 17135번: 캐슬 디펜스

문제 링크:

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

17135번: 캐슬 디펜스

 

문제 설명:

게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 

격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있고 이 성에는 최대 3명의 궁수가 있다.

각각의 턴마다 궁수는 적 하나를 공격하는데 같은 적으로 공격할 수도 있다. (궁수는 동시에 공격하기 때문에 하나의 적이 2명의 궁수에게 맞을 수 있다.)

궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다.

궁수의 공격이 끝나면, 적이 이동한다. 적은 성에 도착하거나, 궁수가 쏜 화살에 맞으면 사라진다.

궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

 

접근 방법:

1. 남은 적이 있는지 확인한다. 남은 적이 없다면 break; 

2. 궁수가 가장 가까운 적을 찾는다.

 => 가장 가까운 적을 찾는 법. 궁수의 위치에서 1~d(궁수가 쏠 수 있는 적 거리)까지 반복문을 사용해 적 있는지 탐색

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

궁수 위치와 거리에 따른 쏠 수 있는 적

따라서 쏠 수 있는 적을 찾는 것은 궁수를 기준으로 왼쪽,궁수 앞,오른쪽으로 나눠서 왼쪽에서 오른쪽으로 탐색하면서 찾았다.

 => 이 때 궁수가 적을 찾고 바로 쏘지 않아야 하는데, 이는 여러 궁수가 같은 적을 쏠 수 있기 때문에, 만약 바로 쏘게 된다면 원래는 같은 적을 쏴야하는 궁수가 다른 적을 쏘게 될 수 있다.

3. 궁수가 쏠 수 있는 적이 있다면 적을 쏜다. 

4. 적들이 전진하고, 만약 전진한 적이 성에 도착했다면 적을 없앤다.

 

소스코드:

/*
17135번: 캐슬 디펜스
https://www.acmicpc.net/problem/17135
*/

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

#define sync_off                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

using namespace std;

int n, m, d;
vector<vector<bool>> map;
int start_remain_enemy = 0;

void initialize()
{
	cin >> n >> m >> d;
	map.resize(n, vector<bool>(m, false));

	int temp;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> temp;
			if (temp) {
				start_remain_enemy++;
				map[i][j] = true;
			}
			else {
				map[i][j] = false;
			}
		}
	}
}

// 좌표가 유효하고, 그 좌표에 적이 있는지 확인
bool check_enemy(int y, int x) {
	if (y >= 0 && y < n && x >= 0 && x < m) {
		if (map[y][x]) {
			return true;
		}
	}
	return false;
}

// 1에서 d까지 왼쪽->오른쪽 방향으로 탐색하면서 쏠 수 있는 적 찾기
pair<int, int> find_enemy(int archer) {
	int my = n, mx = m;
	int y;

	for (int len = 1; len <= d; len++) {

		//궁수 기준으로 왼쪽
		y = n - 1;
		for (int left = len - 1; left >= 1; left--) {
			if (check_enemy(y, archer - left)) {
				my = y, mx = archer - left;
				goto b;
			}
			y--;
		}

		//궁수의 x좌표
		if (check_enemy(n - len, archer)) {
			my = n - len, mx = archer;
			goto b;
		}

		// 궁수 기준으로 오른쪽
		y++;
		for (int right = 1; right <= len - 1; right++) {
			if (check_enemy(y, archer + right)) {
				my = y, mx = archer + right;
				goto b;
			}
			y++;
		}
	}

b:
	return { my,mx };
}

void solve()
{
	int max_remove = -1;

	//백트래킹으로 찾아도 될거같긴 한데, 궁수가 3명으로 정해져 있으니까 걍 반복문 써서 품.
	for (int archer1 = 0; archer1 < m - 2; archer1++) {
		for (int archer2 = archer1 + 1; archer2 < m - 1; archer2++) {
			for (int archer3 = archer2 + 1; archer3 < m; archer3++) {
				vector<vector<bool>> save = map;

				int cur_remove = 0;
				int cur_remaind_enemy = start_remain_enemy;

				while (1)
				{
					//적이 없으면 break
					if (cur_remaind_enemy == 0) {
						break;
					}

					// 궁수가 가장 가까운 적을 찾는다.
					queue<pair<int, int>> que;
					que.push(find_enemy(archer1));
					que.push(find_enemy(archer2));
					que.push(find_enemy(archer3));

					// 궁수가 가장 가까운 적을 쏜다.
					while (!que.empty())
					{
						int y = que.front().first;
						int x = que.front().second;
						que.pop();

						// 쏠 수 있는 적이 없는 경우
						if (y == n || x == m)    continue;

						// 여러 궁수가 같은 적을 노렸을 수도 있으므로, 이미 다른 궁수가 쏜 적이면 넘긴다.
						if (map[y][x])
						{
							map[y][x] = false;
							cur_remove++;
							cur_remaind_enemy--;
						}
					}

					//적들이 전진한다.
					//전진 후 성에 도착한 적은 사라진다.
					for (int j = 0; j < m; j++)
					{
						if (map[n - 1][j])
							cur_remaind_enemy--;
					}
					for (int i = n - 2; i >= 0; i--)
					{
						for (int j = 0; j < m; j++)
						{
							map[i + 1][j] = map[i][j];
						}
					}

					//뭔가 여기 코드 맨 처음 말고는 괜히 시간만 더 걸리게 하는 것 같다. 그래도 최대 15번밖에 안돌아가니까 걍 씀
					for (int j = 0; j < m; j++)
					{
						map[0][j] = false;
					}
				}

				if (max_remove < cur_remove)   max_remove = cur_remove;
				map = save;
			}
		}
	}

	cout << max_remove;
}

int main()
{
	sync_off;

	initialize();
	solve();

	return 0;
}

결과: