[최단경로] 백준 1446번 지름길 자바 (Java)

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

1446번: 지름길

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

코드

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

public class No1446 {
    static class Shortcut{
        int start;
        int end;
        int dist;
        Shortcut(int start, int end, int dist){
            this.start = start;
            this.end = end;
            this.dist = dist;
        }
    }
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int D = sc.nextInt();
        ArrayList<Shortcut> path = new ArrayList<>();

        for(int i = 0; i < N; i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            int dist = sc.nextInt();
            if (end > D) //종료지점이 고속도로 거리를 넘어가서는 안된다
                continue;
            if (end - start > dist)// 지름길이 최단거리일 경우에만 add
                path.add(new Shortcut(start, end, dist));
        }

        Collections.sort(path, new Comparator<Shortcut>() {
            public int compare(Shortcut o1, Shortcut o2) {
                if (o1.start == o2.start){
                    return Integer.compare(o1.end, o2.end);
                }  //시작 지점이 같으면 종료 지점을 기준으로 정렬
                return Integer.compare(o1.start, o2.start);
            }
        });

        int[] distance = new int[D+1];
        int move = 0;
        int idx = 0;
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[0] = 0;


        while (move < D){
            if (idx < path.size()){
                Shortcut s = path.get(idx);
                if (move == s.start){
                    distance[s.end] = Math.min(distance[move] + s.dist, distance[s.end]);
                    idx++;
                } else {
                  distance[move + 1] = Math.min(distance[move + 1], distance[move] + 1);
                  move++;
                }
            } else {
                distance[move + 1] = Math.min(distance[move + 1], distance[move] + 1);
                move++;
            }
        }
        System.out.println(distance[D]);

    }
}

풀이

지름길을 입력 받을때 지름길이 목표지점을 넘어서거나 지름길이 기존 길보다 거리가 긴 경우는 제외 하고 입력받는다.

다익스트라를 이용하여 탐색을 한다. 지름길로 갔을 때와 일반 길로 갔을 때를 비교하여 더 짧게 이동할 수 있을 때에만 distance를 갱신한다.

 

최단경로 푸는 방법

문제유형	푸는 방법
가중치 개념이 없는 최단 경로 문제	BFS
가중치 개념이 있는 한 노드 기준 최단 경로 문제	다익스트라
가중치 개념이 있는 여러 노드 기준 최단 경로 문제	플로이드 와샬