[백준/Java] 1446번 지름길

-Code

import java.io.*;
import java.util.*;

public class BOJ1446 {
    static class Shortcut {
        int next, dist;

        public Shortcut (int next, int dist) {
            this.next = next;
            this.dist = dist;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int cnt = Integer.parseInt(st.nextToken());
        int targetDist = Integer.parseInt(st.nextToken());

        Map<Integer, ArrayList<Shortcut>> shortcutMap = new HashMap<>();
        for (int i = 0; i < cnt; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int next = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());
            // 지름길 집어넣기
            ArrayList<Shortcut> shortcuts = shortcutMap
                    .getOrDefault(start, new ArrayList<>());
            shortcuts.add(new Shortcut(next, dist));
            shortcutMap.put(start, shortcuts);
        }

        int[] highWay = new int[targetDist + 1];
        Arrays.fill(highWay, Integer.MAX_VALUE);
        // 시작값 셋팅
        highWay[0] = 0;
        for (int i = 0; i <= targetDist; i++) {
            if (i > 0) {
                // 지름길을 안타고 이동한 경우 계산
                highWay[i] = Math.min(highWay[i], highWay[i - 1] + 1);
            }
            // 지름길이 존재하는 경우
            if (shortcutMap.containsKey(i)) {
                ArrayList<Shortcut> shortcuts = shortcutMap.get(i);
                for (Shortcut shortcut : shortcuts) {
                    // 목적지를 안넘어가는 경우 검사
                    if (shortcut.next <= targetDist) {
                        // 다음 위치의 최소값 계산
                        highWay[shortcut.next] = Math.min(
                                highWay[shortcut.next], highWay[i] + shortcut.dist);    
                    }
                }
            }

        }
        System.out.println(highWay[targetDist]);
    }
}

최단거리라고 해서 BFS문제인 줄 알고 하려 했으나 가중치 때문에 로직 만들기가 이상해서 찾아보니 dp문제이고 Map을 통해 하면 좋다는 힌트를 얻었습니다. 그래서 다음날 Map을 가지고 로직을 거의 짰으나 0을 검사 안 해서 문제가 생겨서 해당 부분을 고치니 해결되었습니다.