백준 1430 (공격) - java

문제

https://www.acmicpc.net/problem/1430

다솜이는 누구나 쉽게 게임을 만들 수 있도록 하기 위해 Microsoft에서 출시한 XNA Game Studio Express를 가지고 게임을 만들었다.

다솜이의 게임은 적의 공격에 대비해서 도시를 방어하는 게임이다. 도시에는 탑이 N개가 있다. 각각의 탑은 X-Y좌표 평면위에 존재한다. 또, 탑은 맨 처음에 D의 에너지를 가지고 있고, 탑의 사정거리는 R이다.

탑 주변에 적이 나타나면, 탑은 적을 다음과 같은 방법으로 공격할 수 있다.

일단, 탑은 자신의 에너지를 재분배할 수 있다. 만약 서로 다른 두 탑의 거리가 R보다 작거나 같다면, 둘 중에 한 탑은 다른 탑에게 에너지를 자기가 가지고 있는 한도내에서 자유롭게 전송할 수 있다. 하지만, 에너지를 전송할 때는, 절반을 잃는다. (탑 1이 탑 2에게 에너지를 10 전송하면, 탑 1은 에너지를 10을 잃고, 탑 2는 에너지를 5 얻는다.)

탑이 적을 공격할 때는, 적과 탑의 거리가 R보다 작거나 같아야한다. 탑에서 적을 공격할 때는, 자신의 모든 에너지를 적을 공격하는데 쓴다. 이때 적이 받는 데미지는 에너지의 양과 같다.

적이 받을 수 있는 에너지의 최댓값을 구하는 프로그램을 작성하시오.

 

유형 : BFS

 

접근 방식

• 적의 위치를 기준으로 몇 번에 각 지점에 도달하는지에 따라 데미지 계산

전체 코드

import java.util.*;
import java.io.*;

public class BOJ_1430_공격 {

    static int n;
    static double r,d,x,y;

    static double[][] graph;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        n = Integer.parseInt(st.nextToken());
        r = Double.parseDouble(st.nextToken());
        d = Double.parseDouble(st.nextToken());
        x = Double.parseDouble(st.nextToken());
        y = Double.parseDouble(st.nextToken());


        graph = new double[n+1][2];
        for(int i = 1 ; i <= n ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            graph[i][0] = Double.parseDouble(st.nextToken());
            graph[i][1] = Double.parseDouble(st.nextToken());
        }

        boolean[] v = new boolean[n+1];
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(x,y,0));
        double result = 0;

        while(!q.isEmpty()) {
            Node cur = q.poll();

            for(int i = 1 ; i <= n ; i++) {

                boolean canGo = cal(cur.x,cur.y,graph[i][0],graph[i][1]);

                if(canGo && !v[i]) {
                    v[i] = true;

                    if(cur.count == 0) {
                        result += d;
                    }
                    else {
                        result += (d / Math.pow(2,cur.count));
                    }
                    q.add(new Node(graph[i][0],graph[i][1],cur.count + 1));
                }
            }
        }

        System.out.println(result);
        br.close();
    }

    static boolean cal(double x1, double y1, double x2, double y2) {
        return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2)) <= r;
    }

    static class Node {
        double x;
        double y;
        int count;

        Node(double x, double y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
}