[백준][Gold2]10473 - 인간 대포 - JAVA

[문제]

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

10473번: 인간 대포

 

[풀이]

* 알고리즘 : 다익스트라 알고리즘(https://programmer-chocho.tistory.com/63)

 

1.

출발지와 도착지가 존재하기 때문에(a -> b) 최단 경로 알고리즘을 응용하는 문제다.

최초에 그래프를 어떻게 만들것이냐가 관건이다. 

만들어진 그래프가 있어야 최단 경로를 구한든 말든 할 것이기 때문에;;

 

2.

최단 경로를 구하는 그래프를 만들려면 가중치가 있어야 한다. 인간 대포 문제에서는 가중치가 "시간"이 된다. 

가장 빠른! 경로를 구해야 하기 때문이다. 거리는 같아도 그냥 달려가거나, 대포로 발사되냐에 따라 거리의 이동 시간이 달라진다. 

 

3.

그래프를 만들고 가중치에 의한 최단 경로를 구할것임. 여기서 가중치는 시간. 

그런데 시간은 1.달리거나, 2.대포로 발사되거나 <-- 이 두가지 경우에 따라 달라짐. 

더 빠른 시간을 구해서 가중치로 설정해 놓아야 최단 경로(이 문제에서는 가장 빠른 경로)를 구할 수 있지 않을까?

 

4.

또한, 달리거나 대포로 발사되어 어느 정점이든 이동이 가능하다. 때문에 각 정점마다 자신을 제외한 다른 정점들로의 간선을 만들수 있다. 가중치는 위에 말했든 시간이 될 것이고.

 

[코드]

package com.algorithm.thisiscodingtest.dijkstra;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * 인간 대포
 */
public class Test01 {
    static class Coordinate {
        float x;
        float y;

        public Coordinate(float x, float y) {
            this.x = x;
            this.y = y;
        }
    }

    static class Edge implements Comparable<Edge> {
        int destination;
        float time;

        public Edge(int destination, float time) {
            this.destination = destination;
            this.time = time;
        }

        @Override
        public int compareTo(Edge o) {
            return Float.compare(this.time, o.time);
        }
    }

    public static Coordinate[] coordinateList;
    public static ArrayList<Edge> adjList[];
    public static boolean[] check;
    public static float times[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 출발지 좌표
        StringTokenizer st = new StringTokenizer(br.readLine());
        float x = Float.parseFloat(st.nextToken());
        float y = Float.parseFloat(st.nextToken());
        Coordinate start = new Coordinate(x, y);

        // 도착지 좌표
        st = new StringTokenizer(br.readLine());
        x = Float.parseFloat(st.nextToken());
        y = Float.parseFloat(st.nextToken());
        Coordinate end = new Coordinate(x, y);

        int N = Integer.parseInt(br.readLine());
        coordinateList = new Coordinate[N + 2];
        check = new boolean[N + 2];
        times = new float[N + 2];
        adjList = new ArrayList[N + 2];
        for (int i = 0; i < N + 2; i++) {
            adjList[i] = new ArrayList<>();
        }

        // 정점 좌표들(출발지, 대포들, 도착지)
        coordinateList[0] = start;
        coordinateList[N + 1] = end;
        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            x = Float.parseFloat(st.nextToken());
            y = Float.parseFloat(st.nextToken());
            coordinateList[i] = new Coordinate(x, y);
        }

        // 그래프 만들기
        // 출발지는 대포가 아니기 때문에 무조건 달려가야 함.
        for (int i = 1; i < N + 2; i++) {
            float distance = (float) Math.sqrt(Math.pow(coordinateList[0].x - coordinateList[i].x, 2)
                    + Math.pow(coordinateList[0].y - coordinateList[i].y, 2));
            adjList[0].add(new Edge(i, (float) (distance / 5.0)));
        }

        // 대포에서는 달려가거나, 대포로 발사되거나 빠른 걸로 택1
        for (int i = 1; i < N + 2; i++) {
            for (int j = 0; j < N + 2; j++) {
                float distance = (float) Math.sqrt(Math.pow(coordinateList[i].x - coordinateList[j].x, 2)
                        + Math.pow(coordinateList[i].y - coordinateList[j].y, 2));
                adjList[i].add(new Edge(j, (float) Math.min(distance / 5.0, Math.abs(distance - 50) / 5.0 + 2)));
            }
        }

        dijkstra(0);

        bw.write(times[N + 1] + "\n");

        br.close();
        bw.flush();
        bw.close();
    }

    public static void dijkstra(int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        Arrays.fill(times, Integer.MAX_VALUE);
        pq.add(new Edge(start, 0));
        times[start] = 0;

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            int destination = edge.destination;

            if (check[destination]) {
                continue;
            } else {
                check[destination] = true;
            }

            for (Edge next : adjList[destination]) {
                if (times[next.destination] >= times[destination] + next.time) {
                    times[next.destination] = times[destination] + next.time;
                    pq.add(new Edge(next.destination, times[next.destination]));
                }
            }
        }
    }
}