백준 1446번 지름길 (JAVA)

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

1446번: 지름길

 

저는 해당 문제를 DP를 이용해 문제를 해결하였습니다.

DP[depth][시작 지점]으로 하여 depth는 입력 edge의 인덱스이고 현재온 지점입니다.

해당 depth의 edge의 start가 시작 지점보다 edge가 m 이하라면 이 edge를 넣은 것과 안 넣은 것의 min값을 구하였습니다.

 

package BOJ.MST;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_1446 {

    private static class Edge {

        int start;
        int end;
        int weight;

        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        Function<String, Integer> stoi = Integer::parseInt;
        int result = 0;
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        Edge[] edges = new Edge[n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = stoi.apply(st.nextToken());
            int end = stoi.apply(st.nextToken());
            int weight = stoi.apply(st.nextToken());
            edges[i] = new Edge(start, end, weight);
        }
        Arrays.sort(edges, (o1, o2) -> {
            return o1.start - o2.start;
        });
        int[][] dp = new int[n][10_000+1];
        result = dfs(0, 0,edges, n, m,dp);
        System.out.println(result);
    }

    private static int dfs(int depth, int start, Edge[] edges, int n, int m,int[][] dp) {
        if (depth == n) {
            return m;
        }
        if(dp[depth][start] != 0){
            return dp[depth][start];
        }
        int result = m;
        if (start <= edges[depth].start && edges[depth].end <= m) {
            int distance = dfs(depth + 1, edges[depth].end, edges, n, m,dp)
                - (edges[depth].end - edges[depth].start) + edges[depth].weight;
            result = Math.min(result,distance);
        }
        result = Math.min(result,dfs(depth+1,start,edges,n,m,dp));
        dp[depth][start] = result;
        return result;
    }
}