BJ G4 1277 발전소 설치

BJ G4 1277 발전소 설치

 

 

문제링크

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

1277번: 발전소 설치

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

핵심 컨셉

고려사항

 * 최종적으로 연결해야 할 것은 1번 발전소에서 맨 마지막 N 번 발전소
  -- 이때 발전소 간의 가중치가 있기 때문에 dijkstra 알고리즘을 사용해보자.

 * 그래프 구성
  -- 정점인 발전소의 개수가 1000개로 크지 않으므로 인접 행렬로 처리해도 무방함
  -- 거리 기준으로 발전소 간 그래프를 만들어야 하기 때문에 double[][] 형태로 구성 -- 이 거리가 간선의 가중치
  -- 거리를 구한다고 바로 간선이 연결될 수 있는 것은 아니고 안전을 이유로 전선의 길이 M을 초과할 수 없다.
  -- 또 하나 주의 할 점은 이미 연결이 유지된 발전소들도 있다는 점이다.-- 이 발전소들은 가중치가 0이어야 한다.
  -- 즉 새롭게 연결해야하는 곳에만 가중치가 있다.

 * 거리 구하기
  -- 거리는 피타고라스 정리로 처리
  -- 이 과정에서 두 점의 차이에 제곱을 하는데 최악의 경우 (100000+100000)*(100000+100000)를 처리해야 하므로 int 범위를 넘어간다.

입력사항

 * 발전소의 수 N(1 ≤ N ≤ 1,000)
 * 현재 남아있는 전선의 수 W(1≤ W ≤ 10,000) 
  -- 남아있는 전선의 수라기 보다는 연결이 유지된 발전소의 개수라고 하는 편이 이해가 쉽다.
 * 두 번째 줄에는 제한 길이 M(0.0 < M < 200,000.0)
 * 발전소의 X좌표와 Y좌표(-100,000 ≤ xi,yi  ≤ 100,000)

출력사항

 * 1번 발전소와 N번 발전소를 잇는데 필요한 추가 전선 길이의 최솟값을 1000배하여 출력 
 * (단, 1000배하고 난 후 나머지 소수는 반올림이 아닌 버림)

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

youtu.be/me8_aDfi7Y8

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l4;

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

public class BJ_G4_1277_발전소설치 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

    static int N; // 발전소의 수 N(1 ≤ N ≤ 1,000)
    static int W; // 연결된 전선의 수 W(1≤ W ≤ 10,000)

    static double M; // 제한 길이 M(0.0 < M < 200,000.0)

    static double[][] graph;
    static Point[] points;

    static int INF = 987654321;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        StringTokenizer tokens = new StringTokenizer(input.readLine());

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

        M = Double.parseDouble(input.readLine());
        // 정점들의 정보 가져오기
        points = new Point[N + 1];

        for (int n = 1; n <= N; n++) {
            tokens = new StringTokenizer(input.readLine(), " ");
            // X좌표와 Y좌표(-100,000 ≤ xi,yi ≤ 100,000) - 맨 끝점 두 개의 경우 거리가 int의 범위를 넘어간다.
            int c = Integer.parseInt(tokens.nextToken());
            int r = Integer.parseInt(tokens.nextToken());
            points[n] = new Point(n, r, c);
        }
        // 그래프 초기화 - 각 발전소 간의 거리 계산
        graph = new double[N + 1][N + 1];
        for (double[] row : graph) {
            Arrays.fill(row, INF);
        }

        for (int i = 1; i < N + 1; i++) {
            Point p1 = points[i];
            for (int j = 1; j < N + 1; j++) {
                if (i != j) {
                    Point p2 = points[j];
                    // 두 지점간의 거리 계산
                    double distance = p1.getDistance(p2);
                    // 안전을 위한 거리를 초과하면 안된다.
                    if (distance > M) {
                        continue;
                    } else {
                        graph[j][i] = graph[i][j] = distance;
                    }
                }
            }
        }
        // 연결된 발전소 정보 - 비용 zero
        for (int w = 0; w < W; w++) {
            tokens = new StringTokenizer(input.readLine(), " ");
            int p1 = Integer.parseInt(tokens.nextToken());
            int p2 = Integer.parseInt(tokens.nextToken());
            graph[p1][p2] = graph[p2][p1] = 0;
        }

        /*        System.out.println("그래프 확인");
        for (double[] row : graph) {
            System.out.println(Arrays.toString(row));
        }*/

        dijkstra();
    }

    static void dijkstra() {
        PriorityQueue<Point> pq = new PriorityQueue<>();

        Point[] dist = new Point[N + 1];
        for (int i = 1; i < dist.length; i++) {
            Point p = new Point(i, INF);
            if (i == 1) {
                p.cumDist = 0;
                pq.offer(p);
            }
            dist[i] = p;
        }
        // System.out.println("누적 비용 확인");
        // System.out.println(Arrays.toString(dist));

        // queue 작업
        while (!pq.isEmpty()) {
            Point front = pq.poll();

            for (int i = 1; i < dist.length; i++) {
                // 연결되어있는데 경유해서 가는 비용이 더 작다면 업데이트
                if (graph[front.no][i] != INF && dist[i].cumDist > dist[front.no].cumDist + graph[front.no][i]) {
                    dist[i].cumDist = dist[front.no].cumDist + graph[front.no][i];
                    pq.offer(dist[i]);
                }
            }
        }
        System.out.println(dist[N].cumDist == INF ? -1 : (int) (dist[N].cumDist * 1000));
    }

    static class Point implements Comparable<Point> {
        int no;
        int row, col;
        // 기준 정점에서의 누적 거리
        double cumDist;

        public Point(int no, int row, int col) {
            this.no = no;
            this.row = row;
            this.col = col;
        }

        public Point(int no, double cumDist) {
            this.no = no;
            this.cumDist = cumDist;
        }

        public double getDistance(Point o) {
            // 제곱을 해야하는데 결과값이 int의 범위를 넘어갈 수 있다.
            long d1 = this.row - o.row;
            long d2 = this.col - o.col;
            return Math.sqrt(d1 * d1 + d2 * d2);
        }

        @Override
        public int compareTo(Point o) {
            return Double.compare(this.cumDist, o.cumDist);
        }
    }

    private static String src = "9 3\r\n" +
                                "2.0\r\n" +
                                "0 0\r\n" +
                                "0 1\r\n" +
                                "1 1\r\n" +
                                "2 1\r\n" +
                                "2 2\r\n" +
                                "3 2\r\n" +
                                "3 3\r\n" +
                                "4 1\r\n" +
                                "4 3\r\n" +
                                "1 2\r\n" +
                                "2 3\r\n" +
                                "3 4";
}