[BOJ_1227] 발전소 설치

설명

---

인접리스트 형태로 풀기 위해서 Map이라는 새로운 객체로 각 i,j 번째 행렬의 위치의 노드 위치 값을 저장하고 이를 이용해서 Dijkstra를 구현하였는데 

double dist = Math.sqrt(Math.pow(distX, 2) + Math.pow(distY, 2));

//double dist = Math.sqrt(Math.abs(distX) * Math.abs(distX) + Math.abs(distY) * Math.abs(distY));

 

위에 보이는 해당 코드 형태 때문에 계속 틀렸었습니다. 약간 어이 없는 문제인데 컴퓨터의 부동소수점 표현 방식에 따른 정밀도 문제로 인해서 그렇다고 합니다.

 

적어도 PS를 할 때는 API를 적극 이용하여야 겠습니다.

 

코드

---

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

public class Main {
    static int N,W;
    static double M;
    static List<Data>[] graph;

    static class Map{
        int x;
        int y;
        public Map(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
    static class Data implements Comparable<Data>{
        int to;
        double weight;
        public Data(int to, double weight){
            this.to = to;
            this.weight = weight;
        }
        @Override
        public int compareTo(Data o) {
            return Double.compare(this.weight, o.weight);
        }
    }
public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        N = Integer.parseInt(tk.nextToken());
        W = Integer.parseInt(tk.nextToken());

        tk = new StringTokenizer(in.readLine()," ");

        M = Double.parseDouble(tk.nextToken());

        graph = new ArrayList[N + 1];

        for (int i = 0; i <= N; i++){
            graph[i] = new ArrayList<Data>();
        }
        List<Map> map = new ArrayList<>();
        for (int i = 0; i < N; i++){
            tk = new StringTokenizer(in.readLine()," ");
            map.add(new Map(Integer.parseInt(tk.nextToken()),Integer.parseInt(tk.nextToken())));
        }

        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= N; j++) {
                if(i != j){
                    int distX = map.get(i - 1).x - map.get(j - 1).x;
                    int distY = map.get(i - 1).y - map.get(j - 1).y;
                    double dist = Math.sqrt(Math.pow(distX, 2) + Math.pow(distY, 2));
                    graph[i].add(new Data(j, dist));
                    graph[j].add(new Data(i, dist));
                }
            }
        }
        for (int i = 0; i < W; i++){
            tk = new StringTokenizer(in.readLine()," ");
            int from = Integer.parseInt(tk.nextToken());
            int to = Integer.parseInt(tk.nextToken());
            graph[from].add(new Data(to, 0));
            graph[to].add(new Data(from, 0));
        }

        double res = dijkstra();
        System.out.println((long) (res *1000));
    }

    private static double dijkstra() {
        PriorityQueue<Data> q = new PriorityQueue<>();
        q.offer(new Data(1, 0));

        boolean[] visited = new boolean[N + 1];
        double[] dist = new double[N + 1];
        Arrays.fill(dist, Double.MAX_VALUE);
        dist[1] = 0;

        while (!q.isEmpty()) {
            Data now = q.poll();
            if (visited[now.to]) continue;            
            visited[now.to] = true;

            for (Data next : graph[now.to]) {
                if (!visited[next.to] && dist[next.to] > dist[now.to] + next.weight) {
                    dist[next.to] = dist[now.to] + next.weight;
                    q.offer(new Data(next.to, dist[next.to]));
                }
            }
        }
        return dist[N];
    }
}

 

1277번: 발전소 설치