[백준] - 1277. 발전소 설치

문제

 

풀이

1번 발전소부터 N번째 발전소까지의 최소 비용을 구하는 문제이기 때문에 다익스트라 알고리즘을 사용하여 해결하였다. 먼저 각 발전소의 좌표를 저장(plant)하고, 연결되어 있는지 여부를 저장(connected)하였다. 다음으로 다익스트라 알고리즘을 수행하기 전, 1번부터 각 정점까지의 거리를 나타내는 distance 배열을 연결된 경우에는 0, 연결되지 않은 경우에는 INF로 초기화해주었다.

다익스트라 알고리즘을 수행하면서 가중치를 더해주는 부분은 각 좌표간의 거리이기 떄문에 두 점 사이의 거리를 구하는 공식을 통해 구했다. 추가적으로 인접한 행렬에서 찾는 일반적인 경우와 달리 모든 발전소의 거리를 계속해서 갱신해 줄 필요가 있기 때문에 1~N까지 자기 자신을 제외하고 거리를 갱신해주었다.

풀면서 헤맸던 부분은 다익스트라 알고리즘을 시작하기 전에 시작 지점을 방문체크 한 후 다음 점부터 찾았는데 이럴 경우 다음의 반례가 존재한다.

1 => (0,0)
2 => (-1, -1)
3 => (1,1)

1과 2가 연결

해당 반례에서 1을 먼저 방문체크하고 다음 발전소부터 확인하게 되면 최단비용은 2-3을 잇는 선분의 길이가 된다. 하지만 1에서 3으로 바로 연결하는 경우가 최단 거리이기 때문에 1부터 시작해서 바로 연결하는 거리를 찾아놓는 과정이 필요하다. 따라서 1번 발전소에 대해 방문체크를 따로 하지 않음으로써  1번부터 다른 발전소까지의 직접 잇는 거리가 고려될 수 있도록 했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution1277 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, W;
    static double M, INF = 200001;
    static Point[] plant;
    static boolean[][] connected;

    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        W = Integer.parseInt(input[1]);
        String MLine = br.readLine();
        M = Double.parseDouble(MLine);

        plant = new Point[N + 1];
        connected = new boolean[N + 1][N + 1];

        for (int i = 1; i < N + 1; i++) {
            String[] line = br.readLine().split(" ");
            plant[i] = new Point(Integer.parseInt(line[0]), Integer.parseInt(line[1]));
        }

        for (int i = 0; i < W; i++) {
            String[] line = br.readLine().split(" ");
            connected[Integer.parseInt(line[0])][Integer.parseInt(line[1])] = true;
            connected[Integer.parseInt(line[1])][Integer.parseInt(line[0])] = true;
        }

        System.out.println(dijstra());
    }

    private static long dijstra() {
        double[] distance = new double[N + 1];
        for (int i = 1; i < N + 1; i++) {
            distance[i] = INF;
        }
        distance[1] = 0;
        for (int i = 2; i < N + 1; i++) {
            if (connected[1][i]) distance[i] = 0;
        }

        boolean[] visited = new boolean[N + 1];
        for (int i = 0; i < N; i++) {
            double minDist = INF;
            int cur = 0;
            for (int j = 1; j < N + 1; j++) {
                    if (!visited[j] && minDist >= distance[j]) {
                        minDist = distance[j];
                        cur = j;
                    }
            }
            if (cur == N) break;
            visited[cur] = true;
            for (int j = 1; j < N + 1; j++) {
                if (j == cur) continue;
                int next = j;
                if (distance[next] > distance[cur] + getDistance(cur, next)) {
                    distance[next] = distance[cur] + getDistance(cur, next);
                }
            }
        }
        return (long) (distance[N] * 1000);
    }

    private static double getDistance(int cur, int next) {
        if (connected[cur][next]) return 0;

        Point src = plant[cur];
        Point dest = plant[next];
        double dist = Math.pow(src.x - dest.x, 2) + Math.pow(src.y - dest.y, 2);
        return Math.sqrt(dist);
    }

    static class Point {
        int x;
        int y;

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