[백준] 1446번 지름길 (JAVA)

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

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

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

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class boj1446_지름길 {
    static class spot{
        int start;
        int dist;
        spot(int start, int dist){
            this.start = start;
            this.dist = dist;
        }
    }
    static ArrayList<spot>[] path; // 지름길 정보를 저장하기 위한 리스트
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 0부터 시작해서 D에 도착해야함
        int N = Integer.parseInt(st.nextToken()); // 지름길 갯수
        int D = Integer.parseInt(st.nextToken()); // 고속도로 길이

        int[] distance = new int[D+1]; // 거리
        path = new ArrayList[10001]; // d의 범위 -> 10000보다 작거나 같음
        Arrays.fill(distance,Integer.MAX_VALUE); // 거리배열 최댓값으로 초기화
        for(int i=0;i<10001;i++){
            path[i] = new ArrayList<>();
        }

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()); // 시작위치
            int e = Integer.parseInt(st.nextToken()); // 도착위치
            int dist = Integer.parseInt(st.nextToken()); // 지름길 길이

            // 지름길이 무조건으로 최단거리는 아님. -> 지름길인 경우만 저장한다.
            if(e-s>dist){
                path[e].add(new spot(s,dist));
            }
        }

        // 최단거리 구하기
        distance[0] = 0; // 0->0까지의 이동거리 : 0
        for(int i=1;i<=D;i++){
            if(path[i].size()>0){
                // i지점에 도착하는 지름길이 있다면 ? 지름길 중 가장 최단거리로 갱신해주기
                for(spot s : path[i]){
                    if(distance[s.start]+s.dist > distance[i]) continue; // 이미 갱신되었다면 ?
                    distance[i] = Math.min(distance[i-1]+1,distance[s.start]+s.dist);
                }
                continue;
            }
            distance[i] = distance[i-1]+1;
        }


        System.out.println(distance[D]); // D거리까지 이동하는데 걸리는 최단거리

    }
}

• class spot : 지름길 정보 class
• ArrayList< spot >[] path : 지름길을 저장하기위한 리스트
• int[] distance = new int[D+1] : 최단거리를 저장하기 위한 배열
  ex) distance[5] : 거리 5 까지의 최단거리

우선 입력받은 지름길에 대한 정보를 모두 path 리스트에 저장을 해주었는데 이 때 주의해야할 것은 지름길이라고 무조건 빠른 것은 아니다 ! 따라서 지름길인 경우에만 리스트에 저장해주는 방식으로 입력 단계에서부터 한번 걸러주었다.

이후 distance 배열을 0부터 도착지점인 D까지 탐색하면서 해당 지점에 도착하는 지름길이 있다면 존재하는 지름길 중 ( 지름길이 여러개일수도 있음 ) 가장 최단거리로 갱신해주는 방식으로 진행했고 최종적으로 D거리까지 이동하는데 걸리는 최단거리가 distance[D]에 저장되어 있는 것을 확인할 수 있다.

최단거리 갱신 코드

 for(spot s : path[i]){
        if(distance[s.start]+s.dist > distance[i]) continue; // 이미 갱신되었다면 ?
         distance[i] = Math.min(distance[i-1]+1,distance[s.start]+s.dist);
 }