[백준] 12913: 매직 포션 - JAVA

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

 

풀이

0번 도시에서 1번 도시까지 가장 빠른 시간에 가야 한다.

 

포션을 마실 수 있는데 마시게 되면 한 도시에서 다른 도시로 이동하는데 드는 시간을 반으로 줄일 수 있다.

 

n개의 도시, 포션 사용 가능 개수 k가 주어진다.

 

즉, 이차원배열을 `dist[n][k + 1]`로 선언하여 포션을 사용한 개수마다 체크해주어야 한다.

 

우선 도시마다 걸리는 시간이 모두 양수이기 때문에 0번 도시부터 모든 도시까지 최소 시간을 구할 수 있는 다익스트라 알고리즘을 적용했다.

 

다음 도시로 이동할 때 포션을 쓰지 않는 경우, 쓰는 경우를 나눠 진행해야 한다.

 

포션을 쓰는 경우는 현재 도시에 오는데 쓰인 포션의 개수가 k보다 작은 경우에만 가능하다.

 

---

 

메모리: 14672KB
시간: 128ms
언어: Java 11

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

public class Main {
    static class Node implements Comparable<Node> {
        int v;
        double weight;
        int count;

        public Node(int v, double weight, int count) {
            this.v = v;
            this.weight = weight;
            this.count = count;
        }

        @Override
        public int compareTo(Node o) {
            return Double.compare(this.weight, o.weight);
        }
    }

    static int n, k;
    static int[][] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        graph = new int[n][n];
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < n; j++) {
                int w = line.charAt(j) - '0';
                graph[i][j] = w;
            }
        }

        double answer = dijkstra();
        System.out.println(answer);
    }

    private static double dijkstra() {
        double[][] dist = new double[n][k + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(0, 0, 0));
        dist[0][0] = 0;

        while (!pq.isEmpty()) {
            Node node = pq.poll();

            for (int i = 0; i < n; i++) {
                if (n == node.v) {
                    continue;
                }
                double nextCost = dist[node.v][node.count] + graph[node.v][i];
                if (dist[i][node.count] > nextCost) {
                    dist[i][node.count] = nextCost;
                    pq.add(new Node(i, dist[i][node.count], node.count));
                }

                nextCost = dist[node.v][node.count] + (graph[node.v][i] / 2.0);
                if (node.count < k) {
                    if (dist[i][node.count + 1] > nextCost) {
                        dist[i][node.count + 1] = nextCost;
                        pq.add(new Node(i, dist[i][node.count + 1], node.count + 1));
                    }
                }
            }
        }

        double answer = Integer.MAX_VALUE;
        for (int i = 0; i < k + 1; i++) {
            answer = Math.min(answer, dist[1][i]);
        }

        return answer;
    }

}