백준 1430번: 공격

타워들의 사거리, 좌표, 초기 에너지, 적의 좌표가 주어질 때, 타워는 사거리 내의 적을 공격하거나 에너지를 전부 소비해서 에너지 절반을 사거리 내의 다른 타워에 전달할 수 있다. 적에게 줄 수 있는 데미지의 최대값을 구하는 문제이다.

 

이동할 때마다 에너지가 절반이 되므로 최대한 많은 데미지를 주기 위해 공격 불가능한 타워가 공격 가능한 타워에 최대한 적은 횟수로 이동해야 한다. 이를 위해 적에게 공격 가능한 타워를 기준으로 BFS를 수행하여 특정 타워에 도착하는 최소 이동수를 구한다. 우선 공격 가능한 타워를 찾아 Queue에 넣고 이동 횟수를 0으로 초기화해준다.

static double getDistanceSq(Point p1, Point p2) {
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}

static class Point {
    
    double x, y;
    
    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

int[] dist = new int[N];
Arrays.fill(dist, -1);
Queue<Integer> queue = new LinkedList<>();

for (int i = 0; i < N; i++) {
    if (getDistanceSq(towers[i], enemy) <= R * R) {
        dist[i] = 0;
        queue.add(i);
    }
}

 

 

이후 BFS를 수행하면서 이전에 방문하지 않았으면서 사거리 내에 있는 타워로 이동한다.

while (!queue.isEmpty()) {
    int curr = queue.remove();
    
    for (int next = 0; next < N; next++) {
        if (dist[next] == -1 && getDistanceSq(towers[curr], towers[next]) <= R * R) {
            dist[next] = dist[curr] + 1;
            queue.add(next);
        }
    }
}

 

 

순회 후, 각 타워에 대한 최소 이동 횟수가 구해지며 최종 데미지는 이동 가능한 각 타워별 초기 에너지 * (0.5)^(이동 횟수)를 모두 더한 값이 된다.

double totalDamage = 0;
for (int i = 0; i < N; i++) {
    if (dist[i] != -1) {
        totalDamage += D * Math.pow(0.5, dist[i]);
    }
}

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 공격1430 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()), R = Integer.parseInt(st.nextToken());
        double D = Double.parseDouble(st.nextToken());
        Point enemy = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        Point[] towers = new Point[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            towers[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        
        int[] dist = new int[N];
        Arrays.fill(dist, -1);
        Queue<Integer> queue = new LinkedList<>();
        
        for (int i = 0; i < N; i++) {
            if (getDistanceSq(towers[i], enemy) <= R * R) {
                dist[i] = 0;
                queue.add(i);
            }
        }
        
        while (!queue.isEmpty()) {
            int curr = queue.remove();
            
            for (int next = 0; next < N; next++) {
                if (dist[next] == -1 && getDistanceSq(towers[curr], towers[next]) <= R * R) {
                    dist[next] = dist[curr] + 1;
                    queue.add(next);
                }
            }
        }
        
        double totalDamage = 0;
        for (int i = 0; i < N; i++) {
            if (dist[i] != -1) {
                totalDamage += D * Math.pow(0.5, dist[i]);
            }
        }
        
        System.out.print(totalDamage);
    }
    
    static double getDistanceSq(Point p1, Point p2) {
        return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    }
    
    static class Point {
        
        double x, y;
        
        Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }
}