백준 1277번: 발전소 설치

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

 

x, y 좌표에 놓여진 발전소들을 연결해서 1번 과 n번을 연결하는데 드는 최소 전선 길이를 구하는 문제이다. 이미 연결되어 있는 구간은 전선이 필요하지 않으며, 발전소 간 전선의 최대 길이 m을 초과할 수 없다.

 

발전소 간 전선의 길이 제한이 있기 때문에 여러 발전소를 경유하여 n번째 발전소에 도착할 수 있으며, 추가한 전선의 길이의 합을 구하기 위해 각 발전소 간의 거리를 구해야 한다.

double[][] costs = new double[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        double dis = Math.sqrt(Math.pow(board[i].x - board[j].x, 2) + Math.pow(board[i].y - board[j].y, 2));
        costs[i][j] = dis;
        costs[j][i] = dis;
    }
}

 

이후, 이미 연결되어 있는 부분들은 전선 길이를 0으로 넣어준다.

for (int i = 0; i < w; i++) {
    st = new StringTokenizer(br.readLine());
    int start = Integer.parseInt(st.nextToken()), end = Integer.parseInt(st.nextToken());
    costs[start][end] = 0;
    costs[end][start] = 0;
}

 

 

1번 발전소 부터 n번 발전소까지 전선 길이의 최소합을 구해야 하기 때문에 최소 비용을 위한 다익스트라 알고리즘을 적용하여 가장 짧은 누적 추가 전선 길이의 발전소를 방문하게 한다. 방문한 발전소(이미 최소 거리임)와, 길이 제한 m을 초과하는 길은 사용하지 않는다.

Queue<Entry> pq = new PriorityQueue<>();
pq.add(new Entry(1, 0));
boolean[] visited = new boolean[n + 1];
double[] dist = new double[n + 1];
Arrays.fill(dist, Double.MAX_VALUE);
dist[1] = 0;
while (!pq.isEmpty()) {
    Entry current = pq.remove();
    if (visited[current.next]) {
        continue;
    }
    visited[current.next] = true;
    if (current.next == n) {
        System.out.print((long) (current.distance * 1000));
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (i == current.next) {
            continue;
        }
        if (visited[i]) {
            continue;
        }
        double dis = costs[current.next][i];
        if (dis > m) {
            continue;
        }
        if (dist[i] > current.distance + dis) {
            dist[i] = current.distance + dis;
            pq.add(new Entry(i, dist[i]));
        }
        pq.add(new Entry(i, current.distance + dis));
    }
}

class Entry implements Comparable<Entry> {
        
    int next;
    double distance;
        
    public Entry(int next, double distance) {
        this.next = next;
        this.distance = distance;
    }
        
    @Override
    public int compareTo(Entry o) {
        return Double.compare(this.distance, o.distance);
    }
}

 

 

최종 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class 발전소설치1277 {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), w = Integer.parseInt(st.nextToken());
        double m = Double.parseDouble(br.readLine());
        Position[] board = new Position[n + 1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            board[i] = new Position(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        
        double[][] costs = new double[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                double dis = Math.sqrt(Math.pow(board[i].x - board[j].x, 2) + Math.pow(board[i].y - board[j].y, 2));
                costs[i][j] = dis;
                costs[j][i] = dis;
            }
        }
        for (int i = 0; i < w; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()), end = Integer.parseInt(st.nextToken());
            costs[start][end] = 0;
            costs[end][start] = 0;
        }
        br.close();
        Queue<Entry> pq = new PriorityQueue<>();
        pq.add(new Entry(1, 0));
        boolean[] visited = new boolean[n + 1];
        double[] dist = new double[n + 1];
        Arrays.fill(dist, Double.MAX_VALUE);
        dist[1] = 0;
        while (!pq.isEmpty()) {
            Entry current = pq.remove();
            if (visited[current.next]) {
                continue;
            }
            visited[current.next] = true;
            if (current.next == n) {
                System.out.print((long) (current.distance * 1000));
                return;
            }
            for (int i = 1; i <= n; i++) {
                if (i == current.next) {
                    continue;
                }
                if (visited[i]) {
                    continue;
                }
                double dis = costs[current.next][i];
                if (dis > m) {
                    continue;
                }
                if (dist[i] > current.distance + dis) {
                    dist[i] = current.distance + dis;
                    pq.add(new Entry(i, dist[i]));
                }
                pq.add(new Entry(i, current.distance + dis));
            }
        }
    }
    
    static class Position {
        
        int x, y;
        
        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    static class Entry implements Comparable<Entry> {
        
        int next;
        double distance;
        
        public Entry(int next, double distance) {
            this.next = next;
            this.distance = distance;
        }
        
        @Override
        public int compareTo(Entry o) {
            return Double.compare(this.distance, o.distance);
        }
    }
}