문제
캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 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
풀이
문제 대충 보고 풀었다가 개고생한문제..
쉬운줄 알고 했는데 1시간 걸렸네요
코드의 흐름은 다음과 같습니다
1. 조합을 solve 함수를 통해서 3개를 선택 합니다.
2.kill_enemy함수에서 조합 kill_count 와 remove_count를 선언, 하나는 죽이는거, 하나는 내려와서 성에 도달한 것
3.total_enemy == kill_count + remove_count 가 될떄까지 while로 반복한다.
4.find_enemy_and_killed함수는 bfs를 통해서 각자 죽여야 할 적을 선택
5.각자 vector에 넣어놓은 적을 sort하고 kill한다.(cmp는 거리가 가깝고, y가 작은)
6.map을 move함수 . 이동하는것을 구현하기 귀찮으므로,
5행이라고 하면 5행=4행 ,4행=3행, 3행=2행 .. 으로 하고 0행은 0으로 채운다. 반복하면 끄읕
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
// 백준 17135 캐슬디펜스
#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <utility>
#include <algorithm>
#define MAX 20
using namespace std;
// 순서대로 행, 열, 거리제한
int N, M, D;
deque<int> MAP[MAX];
deque<int> COPY_MAP[MAX];
vector<int> choose;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int max_res = 0;
int total_enemy = 0;
struct enemy {
int x;
int y;
int dis;
};
bool cmp(const enemy& a, const enemy& b) {
if (a.dis > b.dis) {
return a.dis < b.dis;
}
else {
return a.y < b.y;
}
}
void move(int &remove_count) {
for (int i = 0; i < M; i++) {
if (COPY_MAP[N - 1][i] == 1) {
remove_count++;
}
}
for (int i = 0; i < N - 1; i++) {
COPY_MAP[N - 1 - i] = COPY_MAP[N - 2 - i];
}
COPY_MAP[0].clear();
for (int i = 0; i < M; i++) {
COPY_MAP[0].push_back(0);
}
}
void find_enemy_and_killed(int &kill_count) {
vector<enemy> vec[3];
for (int i = 0; i < 3; i++) {
queue<pair<int, int>> q;
int check[MAX][MAX] = { 0 };
q.push(make_pair(N - 1, choose[i]));
check[N - 1][choose[i]] = 1;
bool flag = false;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (COPY_MAP[x][y] == 1) {
enemy temp;
temp.x = x;
temp.y = y;
temp.dis = check[x][y];
vec[i].push_back(temp);
flag = true;
}
if (check[x][y] == D) {
continue;
}
if (flag == true) {
continue;
}
for (int j = 0; j < 4; j++) {
int next_x = x + dx[j];
int next_y = y + dy[j];
if (next_x >= 0 && next_y >= 0 && next_x <= N - 1 && next_y <= M - 1) {
if (check[next_x][next_y] == 0) {
check[next_x][next_y] = check[x][y] + 1;
q.push(make_pair(next_x, next_y));
}
}
}
}
}
for (int i = 0; i < 3; i++) {
if (vec[i].empty())
continue;
sort(vec[i].begin(), vec[i].end(), cmp);
if (COPY_MAP[vec[i][0].x][vec[i][0].y] == 1) {
kill_count++;
COPY_MAP[vec[i][0].x][vec[i][0].y] = 0;
}
}
}
void kill_enemy() {
int kill_count = 0;
int remove_count = 0;
for (int i = 0; i < N; i++)
COPY_MAP[i] = MAP[i];
while (total_enemy != kill_count + remove_count) {
find_enemy_and_killed(kill_count);
move(remove_count);
}
max_res = max(max_res, kill_count);
}
void solve(int index, int count) {
if (count == 3) {
kill_enemy();
return;
}
if (index >= M ) return;
choose.push_back(index);
solve(index + 1, count + 1);
choose.pop_back();
solve(index + 1, count);
}
void input() {
cin >> N >> M >> D;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int temp = 0;
cin >> temp;
if (temp == 1) {
total_enemy++;
}
MAP[i].push_back(temp);
}
}
}
void init() {
ios::sync_with_stdio(false);
cin.tie(0);
}
int main() {
init();
input();
solve(0, 0);
cout << max_res << endl;
}
|
cs |
질문과 훈수는 환영
'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글
| [백준 17837] 새로운 게임 2 (C++) (0) | 2021.08.17 |
|---|---|
| [백준 2206] 벽 부수고 이동하기 (C++) (0) | 2021.08.16 |
| [백준 17140] 이차원 배열과 연산 (C++) (0) | 2021.08.13 |
| [백준 12100] 2048 (Easy) (C++) (0) | 2021.08.12 |
| [백준 20058] 마법사 상어와 파이어스톰 (C++) (0) | 2021.08.11 |