[백준 1446 JAVA] 지름길

그래프 및 다익스트라 알고리즘 문제이다.

 

길의 길이 D가 주어지면 노드가 D만큼 있고 가중치 1으로 1크기차이로 이어져 있다고 생각하면 된다.

1- 2 는 가중치 1로 이어져 있음. 단 역주행이 안되니 단방향 그래프

 

노드를 1씩 증가시키며 해당 노드가 갈 수 있는곳에 길이를 기록해 놓는다.

이때 지름길이 있다면, 지름길 도착지점에 도달하기위한 거리를 기록해 놓는다.

 

지름길이 없다면 전 노드에 +1한 값을 기록해 준다(그래프가 크기 1차이로 이어져있다고 생각하기 때문에)

 

하나의 노드씩 증가하며, 해당 노드에 도달하기 위한 최소치를 알아낸 뒤, 최종적으로 도착점에 기록되어있는 수치를 출력해주면 된다.

 

필요없는 연산을 빼기위해 조건을 추가하여 입력을 받았다.

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


class Road{
    int start,end,distance;
    public Road(int s, int e, int d){
        this.start=s;
        this.end = e;
        this.distance = d;
    }
}
class Main{
    static int sToi(String s){
        return Integer.parseInt(s);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = sToi(st.nextToken());
        int D = sToi(st.nextToken());
        int[] distance = new int[D+1];
        Arrays.fill(distance,10001);
        List<Road> road = new ArrayList<>();
        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int s = sToi(st.nextToken());
            int e = sToi(st.nextToken());
            int d = sToi(st.nextToken());
            if(e>D || e-s<=d){
                continue;
            }
            road.add(new Road(s,e,d));
        }
        road.sort(new Comparator<Road>() {
            @Override
            public int compare(Road o1, Road o2) {
                if(o1.start==o2.start) return o1.end-o2.end;
                return o1.start-o2.start;
            }
        });

        int arrayIdx =0;
        int location =0;
        distance[0] = 0;
        while (location<D){
            if(arrayIdx<road.size()){
                Road r = road.get(arrayIdx);
                if(r.start == location){
                    distance[r.end] = Math.min(distance[r.end],distance[location]+r.distance);
                    arrayIdx++;
                    continue;
                }
            }
            distance[location+1] = Math.min(distance[location+1],distance[location]+1);
            location++;
        }
        System.out.println(distance[D]);
    }
}