[BOJ] 1446번: 지름길

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

1446번: 지름길

 

 

문제

 

입력

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

 

출력

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

 

난이도

실버 1

 

Sol

0부터 목적지까지 1씩 이동하면서 지름길을 통해 이동하는 경로(index)와 이동하지 않는 경로(move)를 비교해서 최단 거리를 기록해나간다

public class B1446_지름길 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(token.nextToken()); // 지름길의 개수
        int D = Integer.parseInt(token.nextToken()); // 고속도로의 길이

        List<Graph> list = new ArrayList<>(); // 노드들을 저장하기 위한 리스트

        for(int i=0; i<N; i++){
            token = new StringTokenizer(bf.readLine());
            int start = Integer.parseInt(token.nextToken());
            int end = Integer.parseInt(token.nextToken());
            int len = Integer.parseInt(token.nextToken());

            if(end > D) continue; // 목적지를 지나쳐 가는 경우 역주행 불가능
            if(end - start <= len) continue; // 지름길이 아닌 경우

            list.add(new Graph(start, end, len));
        }
        // input

        // list 정렬 과정 필요 (comparator)
        Collections.sort(list, new Comparator<Graph>() {
            @Override
            public int compare(Graph o1, Graph o2) {
                if(o1.start == o2.start) return o1.end - o2.end;
                return o1.start - o2.start;
            }
        });

        int index = 0; // 리스트 인덱스 확인 위한 변수
        int move = 0; // 어디까지 진행했는지 확인하기 위함

        int[] dist = new int[101]; // padding(모든 위치와 길이는 10000보다 작거나 같은 자연수)
        Arrays.fill(dist, 10001);
        dist[0] = 0;

        while(move < D){ // 목적지까지 1씩 이동(move) + 지름길을 하나씩 확인(index)하면서 최단 거리를 dist에 저장
            if(index < list.size()){
                Graph g = list.get(index);
                if(move == g.start){
                    dist[g.end] = Math.min(dist[move] + g.len, dist[g.end]);
                    index++;
                } else{
                    dist[move + 1] = Math.min(dist[move+1], dist[move] + 1);
                    move++;
                }
            } else {
                dist[move + 1] = Math.min(dist[move + 1] , dist[move] + 1);
                move++;
            }
        }
        // operation

        System.out.println(dist[D]);
        // output
    }

    static class Graph{
        int start; // 시작 위치
        int end; // 도착 위치
        int len; // 지름길의 길이

        public Graph(int start, int end, int len){
            this.start = start;
            this.end = end;
            this.len = len;
        }
    }
}

 

😅

위치 별 최단 거리를 저장하기 위한 dist 배열의 크기를 10000으로 지정해서 계속 오류가 발생했다
→ 인덱스 0~10000의 최단 거리를 저장해줘야 하기 때문에 10001로 지정하여 해결

 

참고

https://jaewoo2233.tistory.com/70