[백준] 17135번 - 캐슬 디펜스 / C++

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 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

 

코드

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

using namespace std;

int N;
int M;
int D;

struct pos
{
	int r;
	int c;

	void init(int r, int c)
	{
		this->r = r;
		this->c = c;
	}

	bool in_range()
	{
		if (r < 0 || c < 0 || c >= M)
			return false;
		return true;
	}
};

struct cmp
{
	bool operator()(pos a, pos b)
	{
		return a.c > b.c;
	}
};

void init(vector<vector<int> > &board, vector<bool> &archer)
{
	int i, j;

	board.resize(N, vector<int>(M));
	for (i = 0; i < board.size(); i++)
	{
		for (j = 0; j < board[0].size(); j++)
		{
			cin >> board[i][j];
		}
	}
	for (i = 0; i < M - 3; i++)
	{
		archer.push_back(false);
	}
	for (i = M - 3; i < M; i++)
	{
		archer.push_back(true);
	}
}

void find_target(vector<vector<int> > &board, queue<pos> &target, int archer)
{
	queue<pos> q;
	priority_queue<pos, vector<pos>, cmp> cand;	// 제거할 후보가 되는 적
	vector<vector<bool> > visit;			// 방문 여부 표시
	pos curr, next;
	int dr[] = {0, -1, 0};
	int dc[] = {-1, 0, 1};
	int i, s, size, d = 1;

	visit.resize(N, vector<bool>(M, false));
	curr.init(board.size() - 1, archer);		// 궁수의 바로 앞의 좌표 (d = 1)
	if (board[curr.r][curr.c])			// 궁수의 바로 앞에 적이 있다면 제거 대상으로 선택
	{
		target.push(curr);
		return;
	}
	q.push(curr);
	visit[curr.r][curr.c] = true;
	while (!q.empty() && d++ < D)			// 가장 가까운 적을 찾아 후보로 등록
	{
		size = q.size();
		for (s = 0; s < size; s++)		// 같은 거리의 칸을 모두 확인함
		{
			curr = q.front();
			q.pop();
			for (i = 0; i < 3; i++)
			{
				next.init(curr.r + dr[i], curr.c + dc[i]);
				if (!next.in_range())
					continue;
				if (visit[next.r][next.c])
					continue;
				if (board[next.r][next.c])
					cand.push(next);
				q.push(next);
				visit[next.r][next.c] = true;
			}
		}
		if (!cand.empty())			// 가장 가까운 적을 찾은 경우
		{					// 가장 왼쪽에 있는 적을 제거 대상으로 선택
			target.push(cand.top());
			return;
		}
	}
}

int game(vector<vector<int> > board, vector<bool> archer)
{
	queue<pos> target;
	pos p;
	int i, cnt = 0;

	while (!board.empty())
	{
		// 각각의 궁수가 제거할 수 있는 적을 찾아 target에 삽입
		for (i = 0; i < archer.size(); i++)
		{
			if (archer[i])
				find_target(board, target, i);
		}
		// target을 확인해 적을 제거 (중복으로 선택된 적은 한 번만 제거)
		while (!target.empty())
		{
			p = target.front();
			target.pop();
			if (board[p.r][p.c])
			{
				board[p.r][p.c] = false;
				cnt++;
			}
		}
		// 마지막 행을 삭제 (모든 적이 아래로 한 칸씩 이동하는 효과)
		board.pop_back();
	}
	// 제거한 적의 수를 리턴
	return cnt;
}

int main()
{
	vector<vector<int> > board;
	vector<bool> archer;
	int answer = 0;

	cin >> N >> M >> D;
	init(board, archer);	// 초기화
	do			// 모든 경우에 대해 게임을 실행하여 제거한 적의 최댓값을 구함
	{
		answer = max(answer, game(board, archer));
	} while (next_permutation(archer.begin(), archer.end()));
	cout << answer << endl;
	return 0;
}

 

순열을 사용하여 가능한 모든 경우에 대해 game()을 실행하고, 각각의 game()에서 제거한 적의 수의 최댓값을 구한다.

game()에서는 각각의 궁수가 제거할 수 있는 적을 찾아 target에 삽입하고 중복을 고려하여 적을 제거한다. 적을 제거한 후에는 모든 적을 한 칸씩 아래로 이동시키는 효과를 내기 위해 board의 마지막 행을 삭제한다. 궁수가 위치한 행은 board.size()로 구하며, 마지막 행보다 한 칸 아래에 있다. 

제거할 적을 찾을 때는 bfs를 사용한다. 탐색 거리를 D 이하로 제한하고 가장 가까운 적을 찾을 때까지 탐색을 수행한다. 같은 거리에 여러 적이 존재할 수 있다. 이때 가장 왼쪽의 적을 제거 대상으로 선택하기 위해 우선순위 큐에 열의 값에 대해 오름차순으로 저장한다. 따라서 우선순위 큐의 첫 번째 원소가 제거할 적의 좌표이다.

다음은 N = 5, M = 5, D = 2이고 궁수를 0번, 3번, 4번 행에 배치한 경우 게임이 진행되는 과정을 나타낸다.

target [(4, 0)(4, 3)(4, 3)], cnt = 2

 

target = [(3, 2)], cnt = 3

 

target = [(2, 2)], cnt = 4

 

target = [(3, 1)(3, 1)], cnt = 5

 

target = [(0, 1)], cnt = 6

 

링크

17135번: 캐슬 디펜스

inbdni/Baekjoon