[BaekJoon] 10473 인간 대포 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static Point start;
    static Point end;
    static int artilleryNum;
    static List<Point> points; // 현재 위치한 곳, 목적지, 대포 위치들
    static Map<Integer, List<Edge>> edges; // 각 위치와 연결된 위치들까지 걸리는 시간들을 나타내는 Map

    static void input() {
        Reader scanner = new Reader();

        points = new ArrayList<>();
        edges = new HashMap<>();
        start = new Point(scanner.nextDouble(), scanner.nextDouble(), false);
        points.add(start);
        end = new Point(scanner.nextDouble(), scanner.nextDouble(), false);

        artilleryNum = scanner.nextInt();
        for (int cnt = 0; cnt < artilleryNum; cnt++) {
            Point artillery = new Point(scanner.nextDouble(), scanner.nextDouble(), true);
            points.add(artillery);
        }

        points.add(end);
    }

    /*
     * 최소 거리를 구하는 다익스트라 알고리즘을 이용하여 문제를 해결한다
     * 이 문제에서는 최소 거리가 아닌 최소 시간을 구해야하기 때문에 간선의 가중치를 시간으로 둔다
     * 한 위치에서 다른 위치들까지 모두 이동할 수 있기 때문에 각 위치까지 간선을 이어주는데,
     * 이때 걸어갈 수도 있고 대포를 이용하여 갈 수도 있기 때문에 두 경우 중 더 시간이 적게 걸리는 경우를 찾아 해당 시간을 가중치로 하여 간선을 생성한다
     *  - 만약 시작 위치가 대포인 위치가 아니라면 대포를 이용할 수 없으니 걸어가는 경우 걸리는 시간을 이용하고
     *  - 시작 위치가 대포라면 대포를 이용하는 경우와 걸어가는 경우 두 가지 중 더 짧은 시간을 가중치로 취한다
     * 이렇게 만들어진 그래프 정보를 이용하여 다익스트라를 돌리면 최소 시간을 구할 수 있다
     */

    static void solution() {
        makeMap();
        double[] times = dijkstra(0);
        System.out.println(times[points.size() - 1]);
    }

    // 그래프 만들기
    static void makeMap() {
        for (int idx = 0; idx < points.size(); idx++) {
            edges.put(idx, new ArrayList<>());
        }

        // 각 위치부터 다른 모든 위치들까지 간선을 연결한다
        for (int basis = 0; basis < points.size() - 1; basis++) {
            for (int pointIdx = basis + 1; pointIdx < points.size(); pointIdx++) {
                Point basisPoint = points.get(basis);
                Point point = points.get(pointIdx);

                edges.get(basis).add(new Edge(pointIdx, getTime(basisPoint, point, basisPoint.isArtillery)));
                edges.get(pointIdx).add(new Edge(basis, getTime(point, basisPoint, point.isArtillery)));
            }
        }
    }

    // 그래프에서 각 시작 위치부터 도착 위치까지의 시간을 구하는 메서드
    static double getTime(Point start, Point end, boolean isArtillery) {
        // 두 위치 사이의 거리 구하기
        double dist = Math.sqrt(Math.pow(start.x - end.x, 2) + Math.pow(start.y - end.y, 2));
        // 걸을 때는 5m/s로 움직이므로 거리를 5로 나누어 시간을 구한다
        double walkingTime = dist / 5;
        // 만약 시작 위치가 대포인 위치가 아니라면 걸을 때의 시간을 그대로 반환한다
        if (!isArtillery) {
            return walkingTime;
        }

        // 대포를 이용했을 때 시간을 구한다
        double artilleryTime = calculateArtilleryTime(dist);
        // 걸을 때와 대포를 이용할 때의 시간 중 더 짧은 시간을 반환한다
        return Math.min(walkingTime, artilleryTime);
    }

    static double calculateArtilleryTime(double distance) {
        // 거리가 50이라면 대포를 이용하여 떨어진 위치가 도착 위치가 되기 떄문에 대포를 이용하는 시간인 2를 반환한다
        if (distance == 50) {
            return 2;
        }

        // 대포를 이용하는 시간인 2를 초기값으로 두고 남은 거리에 대해 시간을 더해준다
        // 남은 거리는 |거리 - 50|을 통해 구할 수 있으니, 이를 5로 나누어 시간을 구한 후에 더해준다
        double artilleryTime = 2;
        distance = Math.abs(distance - 50);
        artilleryTime += (distance / 5);
        return artilleryTime;
    }

    static double[] dijkstra(int start) {
        Queue<Edge> queue = new PriorityQueue<>();
        double[] times = new double[points.size()];
        Arrays.fill(times, Double.MAX_VALUE);

        times[start] = 0;
        queue.offer(new Edge(start, 0));

        while (!queue.isEmpty()) {
            Edge cur = queue.poll();
            if (times[cur.pointIdx] < cur.time) {
                continue;
            }

            for (Edge next : edges.get(cur.pointIdx)) {
                int nextPoint = next.pointIdx;
                double nextTime = cur.time + next.time;

                if (times[nextPoint] > nextTime) {
                    times[nextPoint] = nextTime;
                    queue.offer(new Edge(nextPoint, nextTime));
                }
            }
        }

        return times;
    }

    static class Point {
        double x;
        double y;
        boolean isArtillery;

        public Point(double x, double y, boolean isArtillery) {
            this.x = x;
            this.y = y;
            this.isArtillery = isArtillery;
        }
    }

    static class Edge implements Comparable<Edge> {
        int pointIdx;
        double time;

        public Edge(int pointIdx, double time) {
            this.pointIdx = pointIdx;
            this.time = time;
        }

        @Override
        public int compareTo(Edge o) {
            if (time < o.time) {
                return -1;
            }
            if (time > o.time) {
                return 1;
            }
            return 0;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}