[Baekjoon/JAVA] 1446 지름길

 

 

간만에 dp 문제를 스스로 풀었다 !!

 

 

소스 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int D = Integer.parseInt(st.nextToken());

        // HashMap 1 : 시작점(key) : 끝점(HashMap2)
        // HashMap 2 : 끝점(key) : 거리
        HashMap<Integer, HashMap<Integer, Integer>> fastRoad = new HashMap<>();
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            int fastD = Integer.parseInt(st.nextToken()); // 지름길 거리

            // 지름길이 목적지보다 멀다면 저장하지 않음
            if (E > D) {
                continue;
            }

            // 해당 시작점에 아직 아무 지름길도 저장되지 않았다면
            if (fastRoad.get(S) == null) {
                // 지름길의 종착지(key)와 거리(value)를 저장함
                HashMap<Integer, Integer> destination = new HashMap<>();
                destination.put(E, fastD);
                fastRoad.put(S, destination);

            // 해당 시작점에 이미 지름길이 저장되어 있다면
            } else {
                HashMap<Integer, Integer> destination = fastRoad.get(S);
                // 종착지마저 똑같은 지름길이 저장되어 있다면
                if (destination.get(E) != null) {
                    // 최소값으로 갱신
                    destination.put(E, Math.min(fastD, destination.get(E)));
                    fastRoad.put(S, destination);
                } else {
                    // 종착지가 다르다면 그냥 새로운 key-value 추가
                    destination.put(E, fastD);
                    fastRoad.put(S, destination);
                }
            }
        }

        // dp 배열 순회
        int[] dp = new int[10001];
        for (int i=0; i<10001; i++) {
            if (i != 0) {
                // 처음 도달했다면 이전 거리 + 1
                if (dp[i] == 0) {
                    dp[i] = dp[i-1] + 1;
                } else {
                    // 이미 지름길로 도착한 곳이라면 최소값으로 갱신
                    dp[i] = Math.min(dp[i], dp[i-1] + 1);
                }
            }

            // 현위치에서 갈 수 있는 지름길이 있는 경우
            if (fastRoad.get(i) != null) {
                for (int end: fastRoad.get(i).keySet()) {
                    // 아직 한 번도 방문한 적 없음
                    if (dp[end] == 0) {
                        dp[end] = Math.min(end, dp[i] + fastRoad.get(i).get(end));
                    } else { // 방문한 적 있음
                        dp[end] = Math.min(dp[end], dp[i] + fastRoad.get(i).get(end));
                    }
                }
            }

        }
        System.out.println(dp[D]);
    }
}

 

요새 HashMap 에 빠져서

뭐만 하면 자꾸 HashMap 을 쓰게 되는 거 같다