백준 1277 - 발전소 설치

문제

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

리뷰

다익스트라를 통해 쉽게 풀이할 수 있는 문제였다.

먼저 $W$개의 이미 연결된 간선은 $0$의 비용을 가지는 것으로 설정하여 그래프에
반영한다. 그리고 발전소들의 좌표 정보를 받은 후 각 발전소간 필요한 비용을
계산하여 모든 가능한 간선을 그래프에 설정해준다.

이후, 다익스트라를 돌리며 $N$으로 향하는 경로일 경우 최단 경로 비용을
갱신하여 결과를 도출할 수 있다.

로직의 시간복잡도는 다익스트라의 $O(ElogV)$로 수렴하고 $E=N^2-N+W$,
$V=N$일 때 $N=1,000$, $W=10,000$ 인 최악의 경우에도 무난히 제한 조건
2초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.List;

import static java.lang.Double.*;
import static java.lang.Integer.parseInt;

public class Main {
    static int N;

    static double[] dist;
    static List<Point> nodes = new ArrayList<>();
    static List<List<Node>> graph = new ArrayList<>();


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

        dist = new double[N + 1];
        double M = parseDouble(br.readLine());

        nodes.add(null);

        int x, y;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            x = parseInt(st.nextToken());
            y = parseInt(st.nextToken());

            nodes.add(new Point(x, y));
        }


        int u, v;

        for (int i = 0; i <= N; i++)
            graph.add(new ArrayList<>());
        while (W-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());
            v = parseInt(st.nextToken());

            graph.get(u).add(new Node(v, 0));
            graph.get(v).add(new Node(u, 0));
        }

        setGraph();
        int result = (int) (dijkstra(1, M) * 1000.0);
        System.out.println(result);
        br.close();
    }


    static void setGraph() {
        Point p1, p2;
        double w;
        for (int i = 1; i < N; i++) {
            p1 = nodes.get(i);

            for (int j = i + 1; j <= N; j++) {
                if (i == j) continue;

                p2 = nodes.get(j);
                w = getDist(p1, p2);

                graph.get(i).add(new Node(j, w));
                graph.get(j).add(new Node(i, w));
            }
        }
    }

    static double getDist(Point p1, Point p2) {
        return Math.sqrt(Math.pow(p2.x - p1.x, 2) + Math.pow(p2.y - p1.y, 2));
    }


    static double dijkstra(int start, double M) {
        Arrays.fill(dist, MAX_VALUE);
        dist[start] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingDouble(n -> n.w));
        pq.offer(new Node(start, dist[start]));

        double totalCost = MAX_VALUE;

        double d;
        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (dist[cur.v] < cur.w)
                continue;

            for (Node next : graph.get(cur.v)) {
                d = dist[cur.v] + next.w;

                if (next.w > M) continue;

                if (dist[next.v] > d) {
                    dist[next.v] = d;

                    if (next.v == N)
                        totalCost = dist[next.v];

                    pq.offer(new Node(next.v, dist[next.v]));
                }
            }
        }

        return totalCost;
    }

    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static class Node {
        int v;
        double w;

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

결과