Baekjoon 17135 캐슬 디펜스

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

소스 결과 1992 KB / 12 ms

언어 C++ 17

출처 Baekjoon

분류 브루트 포스

 

설명

n x m크기의 성이 이 있을 때 사거리가 d인 궁수 셋을 배치해 처리할 수 있는 적의 최대 값을 구하여라.

 

문제를 잘 읽어야 합니다. 문제는 두 번 읽어야 합니다.

주어지는 맵보다 세로가 한 칸 더 길게 있다고 생각하고 풀어야 하는 문제.

놓을 수 있는 궁수는 최대 3명이고, 놓는 위치마다 결괏값이 바뀐다.

또한 궁수는 같은 적을 조준 할 수 있어 같은 적을 죽일 수 도 있다.

문제에서 가장 조심해야 할 조건인, 거리가 같은 적이 있다면, 가장 왼쪽 적을 조준한다. 부분이다.

가로길이만큼 탐색하는 방법도 있지만, bfs를 이용하면 최소 시간으로 계산이 가능했다.

브루트 포스가 적용된 간단한 시뮬레이션 문제다.

 

알고리즘

1. 초기 적 상태를 받는다. 구현의 편의성을 위해 입력되는 값을 거꾸로 받아 가장 가까운 적은 가장 늦게 입력받는다. 즉 배열을 거꾸로 입력 받는다.

2. 재귀를 이용한 조합방식으로 궁수 위치를 설정한다.

3. 궁수 위치가 설정되면, 초기 적 상태를 복사해, 시뮬레이션을 할 적 상태를 넘겨준다.

 3-1. 궁수 위치를 기준으로 BFS를 통해 적을 지정해준다.

 3-2. 적을 제거한다.

4. 모든 적이 사라질 때까지 시뮬레이션을 진행하고 처치된 적 수를 반환한다.

5. 최대 값을 갱신한다.

6. 출력

 

소스코드

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 16;

bool board[MAX][MAX];
bool archer[MAX];
int n, m, d;

int posX[3] = { -1, 1, 0 };
int posY[3] = { 0, 0, 1 };

struct Point {
	short x;
	short y;

	Point() : x(0), y(0) {};
	Point(short x, short y) : x(x), y(y) {};
};

void findEnemy(bool board[MAX][MAX], int pos, int& resX, int& resY) {

	bool visited[10][10] = {};

	queue<Point> q;
	queue<Point> nQ;
	
	int dist = 0;
	bool isOver = false;

	q.push(Point(pos, 0));
	visited[0][pos] = true;

	while (dist < d && !isOver)
	{
		while (!q.empty()) {
			Point cur = q.front();
			q.pop();

			if (board[cur.y][cur.x]) {

				if (resX == -1 && resY == -1) {
					resX = cur.x; resY = cur.y;
				}
				else {
					if (cur.x < resX) {
						resX = cur.x; resY = cur.y;
					}
				}
				isOver = true;
			}

			for (int i = 0; i < 3; i++) {
				short nextX = cur.x + posX[i];
				short nextY = cur.y + posY[i];

				if (0 <= nextX && nextX < m && 0 <= nextY && nextY < n && !visited[nextY][nextX]) {
					visited[nextY][nextX] = true;
					nQ.push(Point(nextX, nextY));
				}
			}
		}

		dist++;

		if (isOver)
			continue;

		while (!nQ.empty()) {
			q.push(nQ.front());
			nQ.pop();
		}
	}
}

bool isContinue(bool board[MAX][MAX]) {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (board[i][j])
				return true;
	return false;
}

int run(bool board[MAX][MAX]) {

	int res = 0;

	while (isContinue(board)) {

		vector<Point> turn;

		for (int pos = 0; pos < m; pos++) {
			if (archer[pos])
			{
				int resX = -1, resY = -1;
				findEnemy(board, pos, resX, resY);

				if (resX != -1 && resY != -1)
					turn.push_back(Point(resX, resY));
			}
		}

		for (unsigned int i = 0; i < turn.size(); i++) {
			Point cur = turn[i];

			if (board[cur.y][cur.x])
				res++;

			board[cur.y][cur.x] = false;
		}

		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				board[j][i] = board[j + 1][i];
	}

	return res;
}

void boardCopy(bool origin[MAX][MAX], bool des[MAX][MAX])
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			des[i][j] = origin[i][j];
}

int play() {

	int maxKill = 0;

	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++)
			{
				bool copyBoard[MAX][MAX] = {};

				archer[i] = archer[j] = archer[k] = true;

				boardCopy(board, copyBoard);
				int totalKill = run(copyBoard);

				archer[i] = archer[j] = archer[k] = false;

				if (maxKill < totalKill)
					maxKill = totalKill;
			}

	return maxKill;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m >> d;

	// 0을 향해 오는 모습으로
	for (int i = n - 1; i >= 0; i--)
		for (int j = 0; j < m; j++)
			cin >> board[i][j];

	cout << play();

	return 0;
}