문제
풀이
백트래킹을 이용한, 구현, 시뮬레이션, 완전 탐색 문제이다.
- 궁수 3명을 배치하는데는 백트래킹을 사용한다. 배치를 완료하면 게임을 시작한다.
- 턴마다 적이 아래로 이동하는 것 보다, 궁수가 위로 이동하는 것이 더 간단하다.
- 각 궁수가 공격할 3명의 적을 탐색한다. 판을 하나하나 검사하면서 적일 경우 현재 궁수와의 거리를 측정한다.
- 현재까지 검색한 궁수와의 최소 거리보다 현재 측정한 거리가 더 가깝다면 타겟을 변경한다. 같다면 타겟들의 y값을 비교하여 더 작은 y값을 가진 타겟을 선택한다.
- 선택된 적은 중복되면 안 되므로 set에 저장된다.
- 선택된 타겟들을 공격하고 현재까지 처치한 적을 갱신한다.
- 궁수줄을 한 칸 위로 이동한다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <climits>
using namespace std;
int N, M, D;
int origin_board[16][16];
int board[16][16];
vector<int> archers;
int answer = 0;
int runGame()
{
int out = 0;
memcpy(board, origin_board, sizeof(origin_board));
// 궁수가 한 칸씩 위로 전진하는 방식으로 게임을 진행하는게 더 간단하다.
int archer_row = N;
while (archer_row >= 1)
{
// 궁수가 선택한 타겟들
// 타겟은 중복할 수 없으므로 set으로 설정
set<pair<int, int>> targets;
for (int i = 0; i < 3; ++i)
{
int current_archer_y = archers[i];
int min_dist = INT_MAX;
pair<int, int> current_target(-1, -1);
for (int x = 0; x < archer_row; ++x)
{
for (int y = 0; y < M; ++y)
{
// 현재 검사하는 칸이 적일 경우만 거리를 검사한다.
if (board[x][y] == 0)
{
continue;
}
int dist = abs(x - archer_row) + abs(y - current_archer_y);
// 현재 궁수와의 사정거리가 D이하일 경우
if (dist <= D)
{
if (min_dist > dist)
{
current_target.first = x;
current_target.second = y;
min_dist = dist;
}
// 최소 거리와 현재 거리가 같다면 y값이 더 작은 타겟을 선택한다.
else if (min_dist == dist)
{
if (current_target.second > y)
{
current_target.first = x;
current_target.second = y;
min_dist = dist;
}
}
}
}
}
// 현재 궁수가 타겟이 있다면 set에 넣는다.
if (current_target != pair<int, int>(-1, -1))
{
targets.insert(current_target);
}
}
// 선택한 타겟들을 공격한다.
for (pair<int, int> target : targets)
{
board[target.first][target.second] = 0;
out++;
}
// 궁수줄을 한 칸 위로 이동한다.
archer_row--;
}
return out;
}
// 백트래킹으로 3명의 궁수를 배치한다.
void BackTracking(int index)
{
// 3명 배치되었다면 게임을 시작한다.
if (archers.size() == 3)
{
answer = max(answer, runGame());
return;
}
for (int i = index + 1; i < M; ++i)
{
archers.push_back(i);
BackTracking(i);
archers.pop_back();
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M >> D;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
cin >> origin_board[i][j];
}
}
for (int i = 0; i < M; ++i)
{
archers.push_back(i);
BackTracking(i);
archers.pop_back();
}
cout << answer;
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준][C++] 9527: 1의 개수 세기 (0) | 2023.11.14 |
---|---|
[백준][C++] 2170: 선 긋기 (0) | 2023.11.13 |
[백준][C++] 14890: 경사로 (0) | 2023.11.10 |
[백준][C++] 11559: Puyo Puyo (1) | 2023.11.09 |
[백준][C++] 20056: 마법사 상어와 파이어볼 (3) | 2023.11.09 |