[백준] BOJ - 1446 지름길 자바 풀이 (실버1)

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

1446번: 지름길

 

나의풀이

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        List<int []> list=new ArrayList<>();
        
        int n=Integer.parseInt(st.nextToken());
        int d=Integer.parseInt(st.nextToken());
        int maxVal=Integer.MAX_VALUE;
        
        for(int i=0;i<n; i++){//n개의 지름길
            st=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());//시작
            int b=Integer.parseInt(st.nextToken());//도착
            int c=Integer.parseInt(st.nextToken());//지름길
            
            if(b>d){//고속도로 길이d 보다 도착점이 크면 역주행 불가. 필요없는 지름길
                continue;
            }
            
            if(b-a <= c){ //그냥 가는거보다 지름길이 더 크면 필요없는 지름길
                continue;
            }
            
            list.add(new int[] {a,b,c}); //리스트에 저장
        }
            
        //람다식으로 comparator 생성하여 리스트를 시작위치가 앞인 순서대로 오름차순 정렬
        Collections.sort(list, (o1, o2)->{return o1[0]-o2[0];});
        
        int [] dist=new int[10001];
        int idx=0; //지름길 방문을 위한 인덱스
        int m=0;//이동한 거리를 저장
        
        //배열의 모든값 동일하게 초기화
        Arrays.fill(dist,maxVal);
        dist[0]=0;
        
        while(m<d){
            if(idx< list.size()){
                int temp[]=list.get(idx);//지름길 하나를 방문. 
                
                if(temp[0]== m){
                    dist[temp[1]]=Math.min(dist[temp[1]], dist[temp[0]]+temp[2]);//도착지점까지의 최소거리: 이미 저장된 거리와, 시작지점+지름길 중에 최솟값 
                    idx++; //다음 지름길로..
                }else{//지름길 구간이 아닌 위치. 
                    dist[m+1]=Math.min(dist[m+1], dist[m]+1);
                    m++;
                }
            }else{//지름길 다 돌았음
                dist[m+1]=Math.min(dist[m+1], dist[m]+1);
                m++;
                
            }
        }
        
        System.out.println(dist[d]);
    }
}

 

Tip.

다익스트라 최단경로 알고리즘을 이용하자!