[백준/BOJ] 백준 17135번 : 캐슬 디펜스

www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

각각의 궁수가 배치되는 모든 경우를 고려하고, 그때 제거하는 적의 수를 센다. 각각의 궁수가 제거할 적을 고르는 방법은 각각의 궁수의 위치에서 bfs를 하여 찾았다. 공격할 대상 후보를 다수로 찾았을때 그 중 왼쪽에 있는 적을 고르는것을 고려하였다. 그리고 각각의 궁수가 중복된 적을 골랐을때 처리하는것도 고려하였다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <deque>
using namespace std;

int n, m, d;
int board[16][15];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

int Attack(vector<int>& attacker)
{
	int ret = 0;

	int temp_board[16][15];

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

	for (int i = 0; i < attacker.size(); i++)
		temp_board[n][attacker[i]] = 1; //궁수 배치

	while (1)
	{
		queue<pair<pair<int, int>, int>> q;

		//각각 궁수의 위치를 큐에 넣는다
		q.push(make_pair(make_pair(n - 1, attacker[0]), 0));
		q.push(make_pair(make_pair(n - 1, attacker[1]), 1));
		q.push(make_pair(make_pair(n - 1, attacker[2]), 2));

		vector<int> attack_check(3, 0); //각각 궁수가 공격할 대상 후보를 찾았는지 체크

		int visited[16][15][3];
		int depth[16][15][3];
		for (int i = 0; i < 16; i++)
			for (int j = 0; j < 15; j++)
				for (int k = 0; k < 3; k++)
				{
					visited[i][j][k] = 0;
					depth[i][j][k] = 0;
				}

		depth[n - 1][attacker[0]][0] = 1;
		depth[n - 1][attacker[1]][1] = 1;
		depth[n - 1][attacker[2]][2] = 1;

		pair<int, int> temp_erase[3]; //궁수가 공격할 대상 후보 저장
		for (int i = 0; i < 3; i++)
			temp_erase[i] = make_pair(987654321, 987654321);


		while (!q.empty())
		{
			pair<int, int> here = q.front().first;
			int here_attacker = q.front().second;
			q.pop();

			if (attack_check[here_attacker] == 1) //공격할 대상 후보를 찾았을때
			{
				//공격할 대상 후보를 또 찾았을때
				if (temp_board[here.first][here.second] == 1 && depth[here.first][here.second][here_attacker] == depth[temp_erase[here_attacker].first][temp_erase[here_attacker].second][here_attacker])
				{
					//그 중 왼쪽에 있는 적을 고른다
					if (here.second < temp_erase[here_attacker].second)
						temp_erase[here_attacker] = here;

					continue;
				}

				else
					continue;
			}

			if (attack_check[here_attacker] == 0)
			{
				//공격할 대상 후보를 처음 찾았을때
				if (temp_board[here.first][here.second] == 1)
				{
					temp_erase[here_attacker] = here;
					attack_check[here_attacker] = 1;
					continue;
				}
			}

			for (int i = 0; i < 4; i++)
			{
				pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

				if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m && visited[there.first][there.second][here_attacker] == 0 && depth[here.first][here.second][here_attacker] + 1 <= d)
				{
					depth[there.first][there.second][here_attacker] = depth[here.first][here.second][here_attacker] + 1;
					visited[there.first][there.second][here_attacker] = 1;

					q.push(make_pair(make_pair(there.first, there.second), here_attacker));
				}
			}

		}

		for (int i = 0; i < 3; i++)
		{
			//temp_board[temp_erase[i].first][temp_erase[i].second] != 0 을 통해 각각의 궁수가 중복으로 적을 지울 경우를 고려한다
			if (temp_erase[i].first != 987654321 && temp_erase[i].second != 987654321 && temp_board[temp_erase[i].first][temp_erase[i].second] != 0)
			{
				temp_board[temp_erase[i].first][temp_erase[i].second] = 0;
				ret++;
			}
		}

		for (int j = 0; j < m; j++) //적들 내려오기
		{
			deque<int> down_temp;
			for (int i = n - 1; i >= 0; i--)
			{
				down_temp.push_back(temp_board[i][j]);
			}
			down_temp.pop_front();
			down_temp.push_back(0);

			for (int i = n - 1; i >= 0; i--)
			{
				temp_board[i][j] = down_temp[(n - 1) - i];
			}
		}

		bool finish = true;

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (temp_board[i][j] == 1) //적이 남아 있을때
				{
					finish = false;
					break;
				}
			}

			if (finish == false)
				break;
		}

		if (finish == true)
			break;
	}

	return ret;
}

int Solve(int before_select, vector<int>& attacker)
{
	//궁수의 배치를 모두 다 했을때
	if (attacker.size() == 3)
	{
		return Attack(attacker);
	}

	//더 이상 궁수를 배치할 수 없을때
	if (before_select >= m - 1)
		return -1;

	int ret = -1;
	for (int i = before_select + 1; i < m; i++)
	{
		attacker.push_back(i);
		ret = max(ret, Solve(i, attacker));
		attacker.pop_back();
	}

	return ret;
}

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

	cin >> n >> m >> d;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
		}
	}
	for (int j = 0; j < m; j++)
		board[n][j] = 0; //성 (궁수가 위치할 수 있는 곳)

	vector<int> attacker;
	cout << Solve(-1, attacker);

	return 0;
}