문제
캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 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
로직은 금방 생각해 낼 수 있는 어려운 문제는 아니였지만 실수 한 부분에 대한 이야기를 하려 한다.
처음에 벡터를 지우면 인덱스 참조가 이상해 지는 것을 염두해서 다른 벡터에 인덱스를 저장 한뒤 해당 벡터를 돌면서 인덱스를 꺼내어 기존 벡터를 지우는 계획을 했으나, 똑같은 것이였다.
이를 테면 del이라는 벡터에 인덱스 0,1,2가 들어갔다고 치자 target이라는 벡터로 부터 0번째 인덱스를 지우고 1번째 인덱스를 지우면 당연히 기존 1번째 인덱스는 0번째로 이동되고 2번째 인덱스가 1번째가 되있으므로 내가 생각하는 기준에서는 2번째 인덱스의 벡터가 지워진다.
그러므로 bool값을 둬서 한꺼번에 false에 해당하는 모든 인덱스를 지우는 방식으로 해야 함.
<오류>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int N,M,D;
int arr[15][15];
bool visit[15];
int maxa = 0;
void DFS(int idx, int cur)
{
if(cur == 3)
{
vector<int> vec;
vector<pair<int,int> > target;
int size = 0;
for(int i = 0; i < M; i++)
{
if(visit[i])
{
vec.push_back(i);
}
}
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
if(arr[i][j] == 1)
{
target.push_back({i,j});
size++;
}
}
}
int result = 0;
while(size != 0)
{
vector<int> del;
for(int i = 0; i < vec.size(); i++)
{
int y = N;
int x = vec[i];
int mina = 987654321;
int d = 0;
int posy,posx,idx;
bool avail = false;
for(int j = 0; j < target.size(); j++)
{
int tary = target[j].first;
int tarx = target[j].second;
int d = abs(y-tary) + abs(x-tarx);
if(d <= D)
{
avail = true;
if( d < mina)
{
idx = j;
posy = tary;
posx = tarx;
mina = d;
}
else if(d == mina)
{
if(tarx < posx)
{
idx = j;
posy = tary;
posx = tarx;
}
}
}
}
if(avail)
{
cout << 1 << endl;
cout <<"인덱스 " << idx << endl;
cout <<"target 값" << target[idx].first<<" , " <<target[idx].second << endl;
bool flag = false;
for(int j = 0; j < del.size(); j++)
{
if(del[j] == idx)
{
flag = true;
}
}
if(!flag)
{
del.push_back(idx);
}
}
}
for(int i = 0; i < del.size(); i++)
{
cout << 2 << endl;
cout <<"인덱스 " << del[i] << endl;
cout <<"target 값" << target[del[i]].first<<" , " <<target[del[i]].second << endl;
target.erase(target.begin()+del[i]);
size--;
result++;
}
vector<int> area;
for(int i = 0; i < target.size(); i++)
{
int ty = target[i].first;
if(ty+1 >= N)
{
area.push_back(i);
}
else
{
target[i].first += 1;
}
}
for(int i = 0; i < area.size(); i++)
{
target.erase(target.begin()+area[i]);
size--;
}
}
if(result > maxa)
{
maxa = result;
}
return;
}
else
{
for(int i = idx+1; i < M; i++)
{
visit[i] = true;
DFS(i,cur+1);
visit[i] = false;
}
}
}
int main(void)
{
cin >> N >> M >> D;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
cin >> arr[i][j];
}
}
for(int i = 0; i < M; i++)
{
visit[i] = true;
DFS(i,1);
visit[i] = false;
}
cout << maxa << endl;
}
<정답 소스>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int N,M,D;
int arr[15][15];
bool visit[15];
int maxa = 0;
struct Node{
int y;
int x;
bool alive;
};
void DFS(int idx, int cur)
{
if(cur == 3)
{
vector<int> vec;
vector<Node > target;
for(int i = 0; i < M; i++)
{
if(visit[i])
{
vec.push_back(i);
}
}
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
if(arr[i][j] == 1)
{
target.push_back({i,j,1});
}
}
}
int result = 0;
while(target.size() != 0)
{
for(int i = 0; i < vec.size(); i++)
{
int y = N;
int x = vec[i];
int idx,posx;
int mina = 987654321;
bool avail = false;
for(int j = 0; j < target.size(); j++)
{
int ty = target[j].y;
int tx = target[j].x;
int d = abs(y-ty) + abs(x - tx);
if(d <= D)
{
avail = true;
if(d < mina)
{
mina = d;
posx = tx;
idx = j;
}
else if(d == mina)
{
if(tx < posx)
{
posx = tx;
idx = j;
}
}
}
}
if(avail)
{
target[idx].alive = 0;
}
}
for(int i = 0; i < target.size(); i++)
{
if(!target[i].alive)
{
result++;
}
}
for(int i = 0; i < target.size(); i++)
{
if(target[i].alive)
{
int ty = target[i].y;
if(ty+1 >= N)
{
target[i].alive = 0;
}
else
{
target[i].y += 1;
}
}
}
int size = 0;
for(int i = 0; i < target.size(); i++)
{
if(!target[i].alive)
{
size++;
}
}
while(size != 0)
{
for(int i = 0; i < target.size(); i++)
{
if(!target[i].alive)
{
target.erase(target.begin()+i);
size--;
}
}
}
}
if(result > maxa)
{
maxa = result;
}
return;
}
else
{
for(int i = idx+1; i < M; i++)
{
visit[i] = true;
DFS(i,cur+1);
visit[i] = false;
}
}
}
int main(void)
{
cin >> N >> M >> D;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
cin >> arr[i][j];
}
}
for(int i = 0; i < M; i++)
{
visit[i] = true;
DFS(i,1);
visit[i] = false;
}
cout << maxa << endl;
}'Algorithm' 카테고리의 다른 글
| 백준 17406번 배열 돌리기 4 (삼성 A형) (0) | 2020.03.05 |
|---|---|
| 백준 17136번 색종이 붙이기 (삼성 A형) (0) | 2020.03.04 |
| 백준 17070번 파이프 옮기기 1 (삼성 A형) (0) | 2020.03.02 |
| 백준 16637번 괄호 추가하기 (삼성 A형) (0) | 2020.03.01 |
| 백준 17825번 주사위 윷놀이 (삼성 기출) (0) | 2020.02.29 |
