BOJ01446 지름길

https://www.acmicpc.net/problem/1446 (opens new window)

이 문제는 그래프 이론을 기반으로 다익스트라 알고리즘을 적용하여 해결 할 수 있다. 하지만 관련 풀이를 살펴보아도 이해가 잘 되지 않아 우선적으로 다이나믹 프로그래밍을 활용하여 해결하였다.

다이나믹 프로그래밍 활용

Path.java

우선 경로 저장을 위한 Path 클래스이다. 시작점과 끝점, 길이의 정보가 담겨 관리된다.

private static class Path {
    private final int start;
    private final int end;
    private final int distance;

    public Path(int start, int end, int distance) {
        this.start = start;
        this.end = end;
        this.distance = distance;
    }
}

제출 코드

우선 입력한 값을 검증한 후 저장한다. end의 값이 D킬로미터 이상이면 역주행했다고 판단한다. 또한 start와 end 사이의 차이가 길이보다

for (int i = 0; i < n; i++) {
    int start = scanner.nextInt();
    int end = scanner.nextInt();
    int distance = scanner.nextInt();

    if (end > d) { // 역주행 판단
        continue;
    }

    if (end - start <= distance) { // 지름길이 아니라고 판단
        continue;
    }

    paths.add(new Path(start, end, distance));
}

기본적으로 지름길이 아니면 10킬로미터를 이동하기 위해서는 10킬로미터 전진한다. 하지만 path에 저장된 지름길을 만나게 되면 지름길을 활용하는 편이 더욱 빠르게 도착한다.

for (int i = 1; i <= d; i++) {
    dist[i] = dist[i - 1] + 1;

    for (Path path : paths) {
        if (path.end == i) {
            dist[i] = Math.min(dist[i], dist[path.start] + path.distance);
        }
    }
}

아래는 최종 제출 코드이다.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BOJ1446 {

    private static List<Path> paths = new ArrayList<>();
    private static int[] dist = new int[10_001];

    private static class Path {
        private final int start;
        private final int end;
        private final int distance;

        public Path(int start, int end, int distance) {
            this.start = start;
            this.end = end;
            this.distance = distance;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 지름길의 개수
        int d = scanner.nextInt(); // 고속도로의 길이

        for (int i = 0; i < n; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            int distance = scanner.nextInt();

            if (end > d) { // 역주행 판단
                continue;
            }

            if (end - start <= distance) { // 지름길이 아니라고 판단
                continue;
            }

            paths.add(new Path(start, end, distance));
        }

        for (int i = 1; i <= d; i++) {
            dist[i] = dist[i - 1] + 1;

            for (Path path : paths) {
                if (path.end == i) {
                    dist[i] = Math.min(dist[i], dist[path.start] + path.distance);
                }
            }
        }

        System.out.println(dist[d]);
    }
}

다익스트라 알고리즘 활용

// TODO

#algorithm #BOJ #다이나믹 프로그래밍 #그래프 이론 #다익스트라 #최단 경로 알고리즘 #TODO