[백준] 1277번 - 발전소 설치 (Gold 4)

문제 링크

백준 1277번 - 발전소 설치 (Gold 4)

문제 설명

1번부터 N번까지 N개의 점이 2차원 격자 좌표 위에 있다.
이 중 일부의 점들은 이미 연결이 되어있는 상태이다.
점들을 추가로 이어서 1번 점과 N번 점을 잇고자 하는데, 두 점의 거리가 M을 초과한다면 이을 수 없다.
이 때 1번 점과 N번 점을 잇기 위해 추가로 이은 선분들의 길이의 합의 최솟값을 구하고, 최솟값을 1000배한 값을 소수점 아래를 버림하여 출력하시오.

정답 코드 및 설명

최단 경로를 찾는 문제로 접근할 수 있다.
N개의 노드를 각 점에 대응시키고, 노드 i와 노드 j 사이의 간선의 유무 및 가중치는 아래와 같다.

1. 점 i와 점 j가 이미 이어져있다 : 노드 i와 노드 j 사이에는 가중치가 0인 간선이 있다.
2. 점 i와 점 j 사이의 거리가 M 이하이다 : 노드 i와 노드 j 사이에는 가중치가 두 점 사이의 거리인 간선이 있다.
3. 점 i와 점 j 사이의 거리가 M 초과이다 : 노드 i와 노드 j를 잇는 간선은 없다.

이렇게 구성한 그래프에서 노드 1과 노드 N 사이의 최단 경로를 구하는 문제와 원 문제는 동치이다.
따라서 다익스트라 알고리즘을 적용하여 문제를 해결할 수 있다.
시간 복잡도는 간선 구성에 $O(N^2)$, 다익스트라에 $O(E \log E)$인데 $E = O(N^2)$이므로 전체 시간 복잡도는 $O(N^2 \log N)$이다.
문제에서 N이 1000 이하이므로 시간 제한 2초 안에 충분히 들어온다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ1277 {
    int[][] plants;
    Double[][] dist;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());
        plants = new int[n][2];
        dist = new Double[n][n];
        double m = Double.parseDouble(br.readLine());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            plants[i][0] = Integer.parseInt(st.nextToken());
            plants[i][1] = Integer.parseInt(st.nextToken());
            for (int j = 0; j < i; j++) {
                double d = dSquare(plants[i], plants[j]);
                if (d <= m * m) dist[i][j] = dist[j][i] = Math.sqrt(d);
            }
        }
        while (w-- > 0) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;
            dist[start][end] = dist[end][start] = 0.0;
        }
    }

    double dSquare(int[] p1, int[] p2) {
        double d = (double) (p1[0] - p2[0]) * (p1[0] - p2[0]);
        d += (double) (p1[1] - p2[1]) * (p1[1] - p2[1]);
        return d;
    }

    double Dijkstra() {
        double[] minDist = new double[plants.length];
        for (int i = 0; i < plants.length; i++) {
            minDist[i] = Double.MAX_VALUE;
        }
        class Plant implements Comparable<Plant> {
            final int plantNo;
            final double dist;

            Plant(int plantNo, double dist) {
                this.plantNo = plantNo;
                this.dist = dist;
            }

            @Override
            public int compareTo(Plant p) {
                return Double.compare(this.dist, p.dist);
            }
        }
        PriorityQueue<Plant> pq = new PriorityQueue<>();
        pq.add(new Plant(0, 0));
        while (!pq.isEmpty()) {
            Plant curr = pq.poll();
            int currPlantNo = curr.plantNo;
            double currDist = curr.dist;
            if (minDist[currPlantNo] < currDist) continue;
            for (int i = 0; i < plants.length; i++) {
                if (dist[currPlantNo][i] == null) continue;
                if (currDist + dist[currPlantNo][i] < minDist[i]) {
                    minDist[i] = currDist + dist[currPlantNo][i];
                    pq.add(new Plant(i, minDist[i]));
                }
            }
        }
        return minDist[plants.length - 1];
    }

    void solution() throws IOException {
        input();
        System.out.println((int) (Dijkstra() * 1000));
    }

    public static void main(String[] args) throws IOException {
        new BOJ1277().solution();
    }
}