백준 1446번 지름길 S1 - DP, 다익스트라

 

설날이 벌써 다가오네오

 

문제가 너무 간단해 보였는데.. 진짜 한참 한참 걸린 문제다.

열받으면서 풀었는데 까먹을까봐 까먹을랑 말랑할때 정리한다.

 

 

먼저 지름길 갯수와, 거리가 주어진다.

지름길은 시작점과 끝점, 소모되는 시간이 주어지고 지름길이 오히려 더 길게되는 경우도 존재한다.

또한 고속도로이므로 역주행은 불가능하다. 150이 도착지점이면 정확히 150이어야 한다.

일반 고속도로의 경우 1당 1의 거리를 지닌다.

 

최솟값을 찾아야 하므로 효율이 좋은 지름길을 활용해서 도착점에 도달하면 되겠다.

 

 

초기에 이차원 배열을 통해 DP로 해결하려 접근했었다.

지름길을 통하면 이전에 대한 값과 비교해서 업데이트하고, 다시 그 이후의 길을 업데이트 하는식으로 말이다.

예제는 전부 옳게되었으나 문제가 발생했다. 지름길이 겹치는 경우였다.

 

로직은 이러했다.

지름길을 오름차순으로 정렬하고, 지름길의 초기값은 모두 해당 위치의 거리로 초기화 해주었다.

ex) 10 50 30 이라면 10은 10, 50에는 10 + 30 이 들어가게 말이다.

그 이후, 처음부터 끝까지 1씩 증가하며 지름길로 인해 줄어든곳들을 업데이트 해주는 방식을 통했으나

오류가 발생했다. 한번에 지름길을 모두 입력했기 때문이었다.

 

이 방식은 지름길로 업데이트 할 때마다, 모든 길을 수정 해주어야했다.

한참을 찾다가 방법을 바꾸어 아예 0부터 도착점까지 반복하면서 지름길을 찾으면 업데이트 하는것으로 경로를 바꿔주었다. 또한 배열을 통해 start, end, distance를 관리했지만 객체를 만들어 사용해 주었다.

 

• 정리
• 먼저 효율적인 지름길들만 남긴다.
• 오름차순으로 정렬하며, 같다면 도착지점이 빠른 순서로 정렬한다.
• while문을 통해 시작부터 종료까지 모든 경우를 거리 1마다 업데이트 해준다.

 

import java.util.*;
import java.io.*;
 
public class Main { // Boj_1446_지름길
    public static int N, D, answer, now, idx;
    public static int[] dp;
 
    static class Way {
        int start;
        int end;
        int distance;
 
        // 지름길 객체
        Way(int start, int end, int distance) {
            this.start = start;
            this.end = end;
            this.distance = distance;
        }
 
        // 디버깅용
        @Override
        public String toString() {
            return "Way{" + "start=" + start + ", end=" + end + ", distance=" + distance + '}';
        }
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        ArrayList<Way> short_way = new ArrayList<>();
        dp = new int[D + 1];
        Arrays.fill(dp, 10001);
        dp[0] = 0; // dp[0] 초기화 필수
        now = 0;
        idx = 0;
        // 인풋
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int distance = Integer.parseInt(st.nextToken());
            // 지름길이 효율적이지 않거나, 도착지점이 D보다 크면 받지 않음
            if (end > D)
                continue;
            if (end - start <= distance)
                continue;
            short_way.add(new Way(start, end, distance));
        }
 
        // 시작점이 먼저 오게 정렬, 같다면 종료가 빠른 순서로
        Collections.sort(short_way, new Comparator<Way>() {
            public int compare(Way o1, Way o2) {
                if (o1.start == o2.start) {
                    return o1.end - o2.end;
                }
                return o1.start - o2.start;
            }
        });
 
//        // 정렬 디버깅용
//        for(int i = 0; i<short_way.size(); i++) {
//            System.out.println(short_way.get(i));
//        }
 
        while (now < D) {
            // 지름길 업데이트
            
            if (idx < short_way.size() && short_way.get(idx).start == now) {
                Way tmp = short_way.get(idx);
                dp[tmp.end] = Math.min(dp[now] + tmp.distance, dp[tmp.end]);
                idx++;
            }
            // 고속도로
            else {
                dp[now + 1] = Math.min(dp[now + 1], dp[now] + 1);
                now++;
            }
        }
 
        System.out.println(dp[D]);
 
    }
}

 

쉬운 문제라 판단했는데 다익스트라를 활용해본적이 없어 난관이었다.