[백준 17135: 캐슬 디펜스] (C++)

삼성 A형 기출 문제

https://www.acmicpc.net/workbook/view/2771

ㄴ캐슬 디펜스

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

 

 

 

 

l 문제

 

1. 캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임

2. 게임이 진행되는 곳은 크기가 N×M인 격자판 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

3. 성을 적에게서 지키기 위해 궁수 3명을 배치 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다.

4. 궁수를 배치한 이후의 게임 진행

 

 

l 게임 진행 순서

 

1. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다. 같은 적이 여러 궁수에게 공격당할 수 있다.

2. 공격받은 적은 게임에서 제외된다.

3. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다.

4. 모든 적이 격자판에서 제외되면 게임이 끝난다.

 

 

l 입력

 

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 3 ≤ N, M ≤ 15 1 ≤ D ≤ 10

둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

 

 

l 출력

 

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

 

 

l 풀이

 

궁수 배치 - DFS 게임 진행 - 구현

시뮬레이션 함수 ( 게임 진행 ) {   1. 모든 적과 배치된 궁수와의 거리 계산   2. while(모두 죽을 때까지 반복)   {     3. Round 진행      for(적)      {         for(궁수)         {             4. 타겟팅             거리 D 이내의 적들 중에서             가장 가깝고, 왼쪽에 있는 적을 타겟         }      }      5. 타겟팅된 적들을 한번에 제거   } } DFS 함수 ( 궁수 배치 ) {   1. 게임 진행 ( 궁수 3명을 모두 배치 )   2. 배치 안한다.   3. 배치 한다. }

타겟팅 여러가지 방법이 있다. 더 효율적인 방법도 분명히 있을 것임. 1. 시계 방향 탐색 매 턴마다 모든 궁수의 위치 (N, Y) 에서 거리 1: (N-1, Y) 거리 2: (N-1, Y-1), (N-2, Y), (N-1, Y+1) 거리 3: (N-1, Y-2), (N-2, Y-1), (N-3, Y), (N-2, Y+1), (N-1, Y+2) 이런 식으로 시계 방향으로 탐색하며 적을 찾는다. 찾는 순간 바로 타겟팅 하면 된다는 장점이 있다. 2. 매번 거리 계산하여 갱신 모든 적과 모든 궁수의 거리를 매번 계산한다. 최적의 경우를 계속 갱신해주는 방식이다. 적과의 거리 계산 아이디어 최초 1회, 모든 적과 궁수의 거리를 계산하여 저장한다. 적은 아래로 1칸 씩 이동하므로 최초 거리 - Round로 현재 거리를 간단하게 구할 수 있다.

 

 

l  코드

 

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

int N, M, D, ans, enemy_cnt;

struct enemy
{
	int x, y, dis[3];
	bool is_dead = false;
};
vector<enemy> enemies;

void simulation(vector<int> &archer_pos)
{
	int i, j, round = 0, catch_cnt = 0, e_cnt = enemy_cnt;
	int target_idx[3];

	// 1. 모든 적과 배치된 궁수와의 거리 계산
	for (auto &e : enemies)
		for (i = 0; i < 3; ++i)
			e.dis[i] = N - e.x + abs(e.y - archer_pos[i]);

	// 2. 모두 죽을때까지 반복
	while (e_cnt > 0)
	{
		for (i = 0; i < 3; ++i) target_idx[i] = -1;
        
        // 3. 라운드 진행
		for (i = 0; i < enemy_cnt; ++i)
		{
           		 // 살아 있는 적인가?
			if (enemies[i].x + round >= N && !enemies[i].is_dead)
			{
				enemies[i].is_dead = true;
				if (--e_cnt) break;
			}
			if (enemies[i].is_dead) continue;

			// 4. 타겟팅
			for (j = 0; j < 3; ++j)
			{
				// D거리 이내의 적
				int dis = enemies[i].dis[j] - round;
				if (dis <= D)
				{
					if (target_idx[j] == -1) target_idx[j] = i;
					else
					{
						enemy &t = enemies[target_idx[j]];
						int last_dis = t.dis[j] - round;

						// 더 가깝다면 변경
						if (last_dis > dis) target_idx[j] = i;
						else if (last_dis == dis)
						{
							// 더 왼쪽에 있다면 변경
							if (t.y > enemies[i].y) target_idx[j] = i;
						}
					}
				}
			}
		}
		// 5. 타겟팅된 적들을 한번에 제거
		for (i = 0; i < 3; ++i)
		{
			if (target_idx[i] !=-1 && !enemies[target_idx[i]].is_dead)
			{
				enemies[target_idx[i]].is_dead = true;
				++catch_cnt;
				--e_cnt;
			}
		}
		++round;
	}
	if (ans < catch_cnt) ans = catch_cnt;
}

void set_archer_pos(int idx, int cnt, vector<int> pos)
{
	if (pos.size() == 3)
	{
 		simulation(pos);

		// 죽음 초기화
		for (auto &e : enemies) e.is_dead = false;
		return;
	}
	if (idx == M) return;
	// 배치 안한다
	set_archer_pos(idx + 1, cnt, pos);
	// 배치 한다
	pos.push_back(idx);
	set_archer_pos(idx + 1, cnt, pos);
}

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

	cin >> N >> M >> D;
	register int i, j, input;
	for (i = 0; i < N; ++i)
	{
		for (j = 0; j < M; ++j)
		{
			cin >> input;
			if (input) enemies.push_back({ i, j });
		}
	}
	enemy_cnt = enemies.size();
	set_archer_pos(0, 3, {});
	cout << ans;
	return 0;
}