들어가며

현대모비스와 함께하는 편안한 주행

간만에 찾은 재미있는 문제입니다.

문제설명

승환이는 2차원 평면 위에서 (0, 0) → (a, b)로 이동해야 합니다. 승환이는 자동차를 타고 단위길이만큼 움직일 때마다 1의 스트레스를 받습니다. 승환이는 현대모비스 로고가 그려진 간판과의 거리가 1 이하인 곳에서는 스트레스를 받지 않는다고 합니다. 간판은 N개 존재해요. 스트레스를 최소화할 수 있는 경로를 찾자.

(-10⁹ ≤ a, b ≤ 10⁹, 0 ≤ N ≤ 2000, 정답과의 절대/상대 오차는 10⁻⁹ 까지 허용)

해설

1. 스트레스를 받지 않는 구간 최소로 하기

먼저 어떻게 하면 스트레스를 받지 않는 구간을 최소로 할 수 있을까를 고민해야겠죠. 먼저 백준에서 제공한 예제를 보면 다음과 같습니다.

-- 입력
4 3
2
0 1
2 2

-- 출력
1.472135955

결과가 왜 1.472135955가 나왔는지 이해해야 합니다. 가장 왼쪽 위가 (0, 0)라고 했을 때, 해당 상황을 그림으로 그려보면 다음과 같습니다.

초기 상황

이 상황에서 가장 스트레스를 받지 않는 경로로 가는 방법을 한번 생각해볼게요. 그럼 다음과 같습니다.

초록색 경로를 생각할 수도 있지만, 그림을 보면 빨간 경로가 더 스트레스를 받는 구간이 더 작습니다. 그럼 빨간 경로의 각 선분에서 스트레스를 받는 구간을 다음과 같이 계산할 수 있어요.

•

첫번째 선분 = 0

•

두번째 선분 = √(2² + 1²) - 1(첫번째 간판 적용 범위) - 1(두번째 간판 적용 범위) = 0.2360679775

•

세번째 선분 = √(2² + 1²) - 1(두번째 간판 적용 범위) = 1.2360679775

•

총합 = 0 + 0.2360679775 + 1.2360679775 = 1.472135955

총합의 결과가 예제의 출력과 같습니다. 즉, 스트레스를 받는 구간을 최대한 줄이기 위해서는 최대한 간판을 중심으로 지나 다녀야 합니다.

2. 간판이 오히려 독이 된다면??

두번째로 생각할 수 있는 가능성은 간판이 저 멀리 떨어져 있는 경우입니다. 간판을 들러서 가는 것이 그냥 도착지로 가는 것보다 더 거리가 멀어서 손해볼 수도 있습니다. 그러므로 시작 지점 - 간판 - 도착 지점을 각각 노드라고 생각하고 다익스트라 알고리즘을 적용해 최소 스트레스를 업데이트하면 최종 지점에 도착했을 때, 최소 스트레스를 구할 수 있습니다.

코드

따라서 문제 이해를 제외하면 단순한 다익스트라 알고리즘을 사용해 푸는 문제가 됩니다.

import java.io.*;
import java.util.*;

public class Main {

    static class Node implements Comparable<Node> {
        int index;
        double cost;

        Node(int index, double cost) {
            this.index = index;
            this.cost = cost;
        }

        public int compareTo(Node other) {
            return Double.compare(this.cost, other.cost);
        }
    }

    static int a, b, N;
    static int[][] signBoard;
    static double[] dist;

    public static void main(String[] args) throws IOException {
        setting();

        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[0] = 0;
        pq.add(new Node(0, 0));

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (dist[cur.index] < cur.cost) continue;

            for (int i = 0; i < N + 2; i++) {
                if (i == cur.index) continue;

                double d = getDistance(cur.index, i);
                if (dist[i] > dist[cur.index] + d) {
                    dist[i] = dist[cur.index] + d;
                    pq.add(new Node(i, dist[i]));
                }
            }
        }

        if (dist[N + 1] == 0) System.out.println(0);
        else System.out.printf("%.9f\n", dist[N + 1]);
    }

    static double getDistance(int from, int to) {
        int[] s = signBoard[from];
        int[] e = signBoard[to];

        double length = Math.hypot(e[0] - s[0], e[1] - s[1]);

        if (from >= 1 && from <= N) length -= 1;
        if (to >= 1 && to <= N) length -= 1;
        return Math.max(length, 0);
    }

    private static void setting() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(br.readLine());

        signBoard = new int[N + 2][2];
        dist = new double[N + 2];
        Arrays.fill(dist, Double.MAX_VALUE);

        signBoard[0] = new int[]{0, 0}; // 출발 지점

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            signBoard[i][0] = Integer.parseInt(st.nextToken());
            signBoard[i][1] = Integer.parseInt(st.nextToken());
        }

        signBoard[N + 1] = new int[]{a, b}; // 도착 지점
    }
}

Loading comments...