BOJ 17135. 캐슬 디펜스

24-02-19

🙇‍♀️[Gold III] 캐슬 디펜스 - 17135

문제 링크

성능 요약

메모리: 2156 KB, 시간: 16 ms

분류

너비 우선 탐색, 브루트포스 알고리즘, 그래프 이론, 그래프 탐색, 구현, 시뮬레이션

제출 일자

2024년 2월 19일 13:17:18

문제 설명

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

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

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

격자판의 두 위치 (r₁, c₁), (r₂, c₂)의 거리는 |r₁-r₂| + |c₁-c₂|이다.

입력

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

출력

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

🚀풀이

로직

궁수를 배치한다.
궁수가 공격한다.
2-1. 중복 공격이 가능하고, 가까운 적이 여럿이면 가장 왼쪽을 공격한다.
적이 아래로 한 칸 이동한다.
3-1. 성으로 이동시 게임에서 제외한다.

이렇게 로직을 생각할 수 있다.
그냥 문제의 조건이다.
이걸 그대로 구현하면 된다.

적은 하나의 구조체로 만들었다.

struct enemy
{
	int y, x, idx;
	bool alive = true;
};

전역 변수들은 다음과 같다.

int n, m, d, archerCnt = 3, killCnt = 0, res = 0;
int archerPos[3] = { 0, 0, 0 };
vector<vector<int>> board;
vector<enemy> enemys, savePoint;

먼저 궁수의 배치부터 생각해보자.

궁수는 같은 곳에 서 있을 수 없다.

궁수의 위치는 중복 없는 순열과 마찬가지이다.

이 방법은 DFS를 이용해서 풀 수 있다.

void DFS(int s, int L)
{
	if (L == archerCnt)
	{
		//for (int i = 0; i < archerCnt; ++i)
		//{
		//	cout << archerPos[i] << " ";
		//}
		//cout << endl;
		// 여기서 궁수의 위치를 결정함.

		while (true)
		{
			if (isEndGame() == true)
				break;
			// 배치를 했으니 공격
			attack();
			// 적들 움직이기
			move();
			// 적들이 맵에 없을 때까지 해야됨.
		}

		res = max(res, killCnt);
		resetGame();
	}
	else
	{
		for (int i = s; i < m; ++i)
		{
			archerPos[L] = i + 1;
			DFS(i + 1, L + 1);
		}
	}
}

궁수의 위치를 정하고 공격하고 움직이는 사이클은 게임이 끝날 때 까지 해야하므로 while을 했다.

게임이 끝났는지 여부는 적들중 살아있는 적이 없을 때 까지로 정했다.

bool isEndGame()
{
	for (int i = 0; i < enemys.size(); ++i)
	{
		if (enemys[i].alive == true)
			return false;
	}

	return true;
}

그리고 attack함수가 이 문제에서 제일 중요한 부분인데 아처가 공격이 가능한지와 중복한 애들 공격할 때 킬 카운트를 중복해서 올리지 않게 주의해야한다.

void attack()
{
	vector<enemy> toDieEnemys;
	// 궁수의 공격은 동시에 이루어진다.
	for (int i = 0; i < archerCnt; ++i)
	{
		// 아처의 위치에서 공격가능한 적을 확인.
		enemy en = canAttackEnemy(archerPos[i]);
		if (en.alive == true)
		{
			toDieEnemys.push_back(en);
		}
	}

	// 여기서 진짜 죽이기
	if (toDieEnemys.size() != 0)
	{
		for (int i = 0; i < toDieEnemys.size(); ++i)
		{
			if (enemys[toDieEnemys[i].idx].alive == true)
			{
				killEnemy(toDieEnemys[i].idx);
				killCnt++;
			}
		}
	}
}

여기서 canAttackEnemy라는 함수를 만들었는데 궁수의 위치에서 가장 가까우면서 가장 왼쪽인 적을 정해주는 함수이다.

enemy canAttackEnemy(int pos)
{
	pair<int, int> archerPos = { n + 1, pos };
	vector<enemy> temp;
	int minDist = 123456789;
	for (int i = 0; i < enemys.size(); ++i)
	{
		int dist = ((n + 1 - enemys[i].y) + abs(enemys[i].x - pos));
		if (dist <= d)
		{
			temp.push_back(enemys[i]);
			minDist = min(minDist, dist);
		}
	}

	if (temp.size() != 0)
	{
		enemy ret = temp[0];
		for (int i = 0; i < temp.size(); ++i)
		{
			int dist = ((n + 1 - temp[i].y) + abs(temp[i].x - pos));

			// 가장 가까운거 해야됨. 그 중 젤 왼 쪽
			if (dist != minDist)
				continue;

			if (((n + 1 - ret.y) + abs(ret.x - pos)) != minDist)
				ret = temp[i];

			if (temp[i].x < ret.x)
			{
				ret = temp[i];
			}
		}

		return ret;
	}

	enemy falseEnemy = { -1, -1, -1, false };
	return falseEnemy;
}

필자는 여기서 실수해서 2시간을 사용했다.

move함수는 간단하게 적들의 위치를 옮겨주기만하면된다.

void move()
{
	for (int i = 0; i < enemys.size(); ++i)
	{
		if (enemys[i].alive == false)
			continue;

		enemys[i].y++;

		if (enemys[i].y >= n + 1)
		{
			killEnemy(i);
		}
	}
}

killEnemy함수도 적을 죽일 일이 많아서 따로 만들었다.

void killEnemy(int idx)
{
	enemys[idx].y = 0;
	enemys[idx].x = 0;
	enemys[idx].alive = false;
}

한 게임이 다 끝났으면 게임을 초기화하고 다시 궁수를 배치해야한다.

게임을 초기화하는 함수는 아래와 같다.

void resetGame()
{
	for (int i = 0; i < savePoint.size(); ++i)
	{
		enemys[i].y = savePoint[i].y;
		enemys[i].x = savePoint[i].x;
		enemys[i].idx = savePoint[i].idx;
		enemys[i].alive = savePoint[i].alive;
	}

	killCnt = 0;
}

초기 입력 상태를 savePoint라는 벡터를 하나 더 만들어서 복사했다.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

struct archer
{
	int pos;
};

struct enemy
{
	int y, x, idx;
	bool alive = true;
};

void setting();
void attack();
void move();
void killEnemy(int idx);
bool isEndGame();
void resetGame();
enemy canAttackEnemy(int pos);
void DFS(int s, int L);
void solve();


// 캐슬 디펜스

// 궁수는 3명
// 최대한 많은 적을 죽여야한다.
// 궁수를 배치하는 경우의 수를 모두 탐색하여 결과 계산하기?

// 로직
// 궁수를 배치한다.
// 궁수가 공격한다.
// 중복 공격이 가능하고, 가까운적이 여럿이면 가장 왼쪽 공격
// 적이 아래로 한 칸 이동
// 성으로 이동시 게임에서 제외

// 궁수의 위치는 중복 없는 순열


int n, m, d, archerCnt = 3, killCnt = 0, res = 0;
int archerPos[3] = { 0, 0, 0 };
vector<vector<int>> board;
vector<enemy> enemys, savePoint;
void setting()
{
	cin >> n >> m >> d;
	board = vector<vector<int>>(n + 1, vector<int>(m + 1));
	int idx = 0;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			cin >> board[i][j];
			if (board[i][j] == 1)
			{
				enemys.push_back({ i, j, idx, true });
				savePoint.push_back({ i, j, idx, true });
				idx++;
			}
		}
	}
}

void attack()
{
	vector<enemy> toDieEnemys;
	// 궁수의 공격은 동시에 이루어진다.
	for (int i = 0; i < archerCnt; ++i)
	{
		// 아처의 위치에서 공격가능한 적을 확인.
		enemy en = canAttackEnemy(archerPos[i]);
		if (en.alive == true)
		{
			toDieEnemys.push_back(en);
		}
	}

	// 여기서 진짜 죽이기
	if (toDieEnemys.size() != 0)
	{
		for (int i = 0; i < toDieEnemys.size(); ++i)
		{
			if (enemys[toDieEnemys[i].idx].alive == true)
			{
				killEnemy(toDieEnemys[i].idx);
				killCnt++;
			}
		}
	}
}

enemy canAttackEnemy(int pos)
{
	pair<int, int> archerPos = { n + 1, pos };
	vector<enemy> temp;
	int minDist = 123456789;
	for (int i = 0; i < enemys.size(); ++i)
	{
		int dist = ((n + 1 - enemys[i].y) + abs(enemys[i].x - pos));
		if (dist <= d)
		{
			temp.push_back(enemys[i]);
			minDist = min(minDist, dist);
		}
	}

	if (temp.size() != 0)
	{
		enemy ret = temp[0];
		for (int i = 0; i < temp.size(); ++i)
		{
			int dist = ((n + 1 - temp[i].y) + abs(temp[i].x - pos));

			// 가장 가까운거 해야됨. 그 중 젤 왼 쪽
			if (dist != minDist)
				continue;

			if (((n + 1 - ret.y) + abs(ret.x - pos)) != minDist)
				ret = temp[i];

			if (temp[i].x < ret.x)
			{
				ret = temp[i];
			}
		}

		return ret;
	}

	enemy falseEnemy = { -1, -1, -1, false };
	return falseEnemy;
}

void move()
{
	for (int i = 0; i < enemys.size(); ++i)
	{
		if (enemys[i].alive == false)
			continue;

		enemys[i].y++;

		if (enemys[i].y >= n + 1)
		{
			killEnemy(i);
		}
	}
}

void killEnemy(int idx)
{
	enemys[idx].y = 0;
	enemys[idx].x = 0;
	enemys[idx].alive = false;
}

bool isEndGame()
{
	for (int i = 0; i < enemys.size(); ++i)
	{
		if (enemys[i].alive == true)
			return false;
	}

	return true;
}

void resetGame()
{
	for (int i = 0; i < savePoint.size(); ++i)
	{
		enemys[i].y = savePoint[i].y;
		enemys[i].x = savePoint[i].x;
		enemys[i].idx = savePoint[i].idx;
		enemys[i].alive = savePoint[i].alive;
	}

	killCnt = 0;
}

void DFS(int s, int L)
{
	if (L == archerCnt)
	{
		//for (int i = 0; i < archerCnt; ++i)
		//{
		//	cout << archerPos[i] << " ";
		//}
		//cout << endl;
		// 여기서 궁수의 위치를 결정함.

		while (true)
		{
			if (isEndGame() == true)
				break;
			// 배치를 했으니 공격
			attack();
			// 적들 움직이기
			move();
			// 적들이 맵에 없을 때까지 해야됨.
		}

		res = max(res, killCnt);
		resetGame();
	}
	else
	{
		for (int i = s; i < m; ++i)
		{
			archerPos[L] = i + 1;
			DFS(i + 1, L + 1);
		}
	}
}

void solve()
{
	setting();

	DFS(0, 0);

	cout << res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

Twitter Facebook LinkedIn

BOJ 17135. 캐슬 디펜스

🙇‍♀️[Gold III] 캐슬 디펜스 - 17135

성능 요약

분류

제출 일자

문제 설명

입력

출력

🚀풀이

🚀전체 코드

공유하기

참고

BOJ 14620. 꽃길

BOJ 13301. 타일 장식물

BOJ 13301. 타일 장식물

BOJ 9934. 완전 이진 트리