Study hard
(c++)백준 17145번: 캐슬 디펜스 본문
[풀이]
문제에 나온 게임 순서대로 구현하였다.
1. 궁수 3명 배치: dfs를 이용하여 궁수 위치의 조합을 만들어 각 조합마다 게임을 진행하였다.
2. 적의 존재 여부 확인 및 적의 위치 저장(적이 존재하지 않으면 게임 끝)
3. 궁수마다 가장 가까운 적 찾아서 공격: 궁수와 가장 가까운 적을 찾고 그 적이 아직 공격받지 않았다면 공격할 수 있는 적의 수로 카운트 해주고 제외한다.
4. 적 아래로 한 칸 이동: 맵의 범위 넘어가면 제외 ※첫번째 줄부터 아래로 내려가면서 이동시키면 맵이 의도한 것과 다른 모양이 될 수 있으므로 마지막 줄부터 위로 올라가면서 이동시켜야 함!!
#include <iostream>
#include <vector>
#include <cstring>//memset
#include <algorithm>//max
#include <cstdlib>//abs
using namespace std;
struct Pos {
int x, y;
};
int N, M, D;
int Map[15][15];
int cMap[15][15];
bool check[15];//궁수 자리
bool killed[15][15];//해당 적이 죽었는지
int Max = -1;
vector<Pos>Archer;//궁수 위치
vector<Pos>Enemy;//적의 위치
void init() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cMap[i][j] = Map[i][j];
}
}
}
bool checkEnemy() {
Enemy.clear();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (cMap[i][j] == 1)
Enemy.push_back({ i,j });
}
}
if (Enemy.size() == 0)
return false;
else return true;
}
void Move() {
for (int i = N-1; i >=0; i--) {
for (int j = 0; j < M; j++) {
if (cMap[i][j] == 1) {
cMap[i][j] = 0;
if (i + 1 != N) {
cMap[i + 1][j] = 1;
}
}
}
}
}
void Game() {
init();
int kill_cnt = 0;
while (checkEnemy()) {//적 존재 여부와 위치 저장
memset(killed, false, sizeof(killed));
//궁수마다 가장 가까운 적 찾아서 공격
for (int i = 0; i < 3; i++) {
int dist = 0;
int Min = 987654321;
int ex, ey;
bool exist = false;
//가장 가까운 적 찾기
for (int j = 0; j < Enemy.size(); j++) {
dist = abs(N - Enemy[j].x) + abs(Archer[i].y - Enemy[j].y);
if (dist > D)
continue;
exist = true;
if (Min > dist) {
Min = dist;
ex = Enemy[j].x;
ey = Enemy[j].y;
}
else if (Min == dist) {
if (Enemy[j].y < ey) {
ex = Enemy[j].x;
ey = Enemy[j].y;
}
}
}
if (exist == false)
continue;
//가장 가까운 적 공격
if (killed[ex][ey] == false) {
killed[ex][ey] = true;
cMap[ex][ey] = 0;
kill_cnt++;
}
}
Move();
}
Max = max(Max, kill_cnt);
}
//궁수 위치 정하고 게임 시작
void dfs(int y, int cnt) {
if (cnt == 3) {
Game();
return;
}
for (int i = y; i < M; i++) {
if (check[i] == true)
continue;
check[i] = true;
Archer.push_back({ N,i });
dfs(i, cnt + 1);
Archer.pop_back();
check[i] = false;
}
}
void solution() {
cin >> N >> M >> D;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> Map[i][j];
}
}
dfs(0, 0);
cout << Max << '\n';
}
int main() {
solution();
return 0;
}
'백준 > bfs, dfs' 카테고리의 다른 글
(c++)백준 17281번: ⚾ (0) | 2020.10.12 |
---|---|
(c++)백준 17136번: 색종이 붙이기 (0) | 2020.10.12 |
(c++)백준 17070번: 파이프 옮기기 1 (0) | 2020.10.11 |
(c++)백준 16637번: 괄호 추가하기 (0) | 2020.10.11 |
(c++)백준 16928번: 뱀과 사다리 게임 (0) | 2020.09.05 |