공격
알고리즘 구분 : 그래프 이론, 그래프 탐색, 기하학, 너비 우선 탐색
문제
다솜이는 누구나 쉽게 게임을 만들 수 있도록 하기 위해 Microsoft에서 출시한 XNA Game Studio Express를 가지고 게임을 만들었다.
다솜이의 게임은 적의 공격에 대비해서 도시를 방어하는 게임이다. 도시에는 탑이 N개가 있다. 각각의 탑은 X-Y좌표 평면위에 존재한다. 또, 탑은 맨 처음에 D의 에너지를 가지고 있고, 탑의 사정거리는 R이다.
탑 주변에 적이 나타나면, 탑은 적을 다음과 같은 방법으로 공격할 수 있다.
일단, 탑은 자신의 에너지를 재분배할 수 있다. 만약 서로 다른 두 탑의 거리가 R보다 작거나 같다면, 둘 중에 한 탑은 다른 탑에게 에너지를 자기가 가지고 있는 한도내에서 자유롭게 전송할 수 있다. 하지만, 에너지를 전송할 때는, 절반을 잃는다. (탑 1이 탑 2에게 에너지를 10 전송하면, 탑 1은 에너지를 10을 잃고, 탑 2는 에너지를 5 얻는다.)
탑이 적을 공격할 때는, 적과 탑의 거리가 R보다 작거나 같아야한다. 탑에서 적을 공격할 때는, 자신의 모든 에너지를 적을 공격하는데 쓴다. 이때 적이 받는 데미지는 에너지의 양과 같다.
적이 받을 수 있는 에너지의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 탑의 개수 N, 사정 거리 R, 초기 에너지 D, 적의 X좌표 X, 적의 Y좌표 Y가 주어진다. 둘째 줄부터는 탑의 위치가 한 줄에 하나씩 X좌표 Y좌표 순으로 주어진다. N은 50보다 작거나 같은 자연수이고, R은 500보다 작거나 같은 자연수, D는 100보다 작거나 같은 자연수이다. 모든 X좌표와 Y좌표는 1,000보다 작거나 같은 음이 아닌 정수이다. 탑의 위치가 같은 경우는 없고, 적과 탑의 위치가 같은 경우도 입력으로 주어지지 않는다.
출력
첫째 줄에 적이 받는 데미지의 최댓값을 출력한다. 절대/상대 오차는 10-2까지 허용한다.
예제 입력 1
4 2 10 0 0
2 0
4 0
6 0
8 0
예제 출력 1
18.75
예제 입력 2
7 3 100 3 0
5 1
6 3
5 5
3 6
1 5
0 3
1 1
예제 출력 2
362.5
예제 입력 3
9 1 4 0 2
1 2
2 2
3 2
4 2
5 2
3 0
3 1
3 3
3 4
예제 출력 3
9.25
예제 입력 4
3 7 17 0 0
0 5
10 10
5 0
예제 출력 4
34.0
예제 입력 5
4 1 100 10 10
10 12
12 10
10 8
8 10
예제 출력 5
0.0
힌트
예제 1: 탑4 -> 탑3 10 전송 탑3 -> 탑2 15 전송 탑2 -> 탑1 17.5 전송 탑1 -> 적 18.75 공격
문제 풀이
적에게 가할 수 있는 최대 피해를 계산하라고 했는데, 여기서 피해량을 좌지우지하는 조건은 에너지 전송부분이다. 즉, 어떤 탑의 위치에서는 적을 공격할 수 없을 때, 다른 탑으로의 에너지 전송을 통해서 적을 공격할 수 있는 탑으로 에너지를 움직여 공격할 수 있게 되는데, 여기서 에너지 전송하는 과정에서 전송마다 50%의 손실이 발생하게 되므로, 이를 최소화하면서 에너지를 공격 가능한 탑으로 옮기라는 문제였다.
먼저, 공격 가능한 탑과 불가능한 탑을 구분해야 된다고 판단하였다.
공격 불가능한 탑에서 공격 가능합 탑까지 이동하는 거리를 BFS를 통해 최솟값을 구해 이를 수학 계산으로 마무리하면 되겠다고 판단하였다.
일반적으로 BFS는 특정 노드를 시작지점으로 하는 탐색인데, 여기서는 공격이 불가능한 탑의 개수가 많을 수 있으므로, 불가능한 탑별로 BFS를 하는 것이 TLE에 걸리지 않을까 고민하였지만, 탑의 최대 개수가 50개였으므로 해당 방식으로 구현해보았다.
공격 불가능한 탑별로 BFS를 돌리는데, 이 때 일반적인 방문 배열로 쓰이는 visited배열이 해당 탑에 도달하는데 걸리는 횟수로 간주하였다. 그렇게 하여, BFS가 끝난 이후, 공격 가능한 탑의 인덱스 정보를 가진 벡터를 반복문으로 visited배열에 갱신되어 있는 접근 횟수를 확인하고, 이 중 최솟값을 찾아 수학 계산하여 result값에 더하는 과정을 반복하였다.
처음에는 플로이드 와샬로의 거리 계산 최적화도 가능할 것이라고 생각하였으나, 구현 방식까지는 명확하게 생각해내지 못해 일반 BFS로 구현했다.
BFS 방식 또한 조금 더 효율적인 구현이 가능할 것 같다는 생각도 든다.
소스 코드
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
int n, r, d, X, Y;
double result = 0;
vector<pair<int, int>> tower;
vector<int> reach; // 도달 가능한 타워들의 idx value
vector<int> notReach; // 도달하지 못하는 타워들의 idx value
int visited[51];
double dist(int x1, int y1, int x2, int y2);
void bfs(int idx);
void solve();
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> r >> d >> X >> Y;
for(int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
tower.push_back({x, y});
// 사정 거리 안에 있는지 여부
if(dist(x, y, X, Y) <= r) {
result += d;
reach.push_back(i);
}
else {
notReach.push_back(i);
}
}
solve();
return 0;
}
double dist(int x1, int y1, int x2, int y2) {
return sqrt(pow(abs(x1 - x2), 2) + pow(abs(y2 - y1), 2));
}
void bfs(int idx) {
queue<int> q;
q.push(idx);
visited[idx] = 0;
while(!q.empty()) {
int now = q.front();
q.pop();
for(int i = 0; i < n; i++) {
// 자기 자신이 dest가 되는 경우 제외
if(now == i) {
continue;
}
// 만약 해당 타워의 거리가 사정거리 이내이면서, 이미 방문하지 않은 경우라면
if(dist(tower[now].first, tower[now].second, tower[i].first, tower[i].second) <= r && !visited[i]) {
q.push(i);
visited[i] = visited[now] + 1;
}
}
}
}
void solve() {
// 탑으로 가지 못하는 정점에 대한 BFS 수행
for(int i = 0; i < notReach.size(); i++) {
memset(visited, 0, sizeof(visited));
bfs(notReach[i]);
int minCnt = 987654321;
for(int j = 0; j < reach.size(); j++) {
if(visited[reach[j]] != 0) {
minCnt = min(visited[reach[j]], minCnt);
}
}
result += (double)d / pow(2, minCnt);
}
cout << fixed;
cout.precision(2);
cout << result << endl;
}- 문제 출처 : https://www.acmicpc.net/problem/1430
- 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.
