백준 1446 - 지름길

Java

1446 번 - 지름길

문제

접근 방법

해당 지점까지 도착하는데 걸리는 비용을 나타내는 dp로 해결하였다.
기본적으로 k까지 위치에 도달하는데 걸리는 비용은 dp[k - 1] + 1 이다.

만약 해당 k 지점에서 지름길의 도착 지점과 동일하다면, 지름길의 시작점에서 지름길의 비용을 더한 값이, 현재 dp[k] 보다 작은지 확인한다.
a : 지름길의 시작
b : 지름길의 도착
c : 지름길의 비용
Math.max(dp[k], dp[k - a] + c)

코드

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

public class Main {
	static int n, result, d;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	d = stoi(stk.nextToken());
    	int[] dp = new int[d + 1];

    	List<int[]> list = new ArrayList<>();

    	int a,b,c;
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		a = stoi(stk.nextToken());
    		b = stoi(stk.nextToken());
    		c = stoi(stk.nextToken());
    		if(b > d)
    			continue;
    		list.add(new int[] {a,b,c});
    	}

    	int len = list.size();
		// 거리 이동 시작
    	for(int i = 1; i <= d; i++) {
    		dp[i] = dp[i - 1] + 1;
			// 지름길 탐색
    		for(int j = 0; j < len; j++) {
				// 현재 위치가, 지름길의 도착지점이라면
    			if(list.get(j)[1] == i) {
					// 지름길의 시작점에서 지름길의 비용을 더해, 기존 비용보다 적은지 확인
    				dp[i] = Math.min(dp[i], dp[list.get(j)[0]] + list.get(j)[2]);
    			}
    		}
    	}

    	System.out.println(dp[d]);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

코드 - 다익스트라

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

public class Main {
	static int n, result, d;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	d = stoi(stk.nextToken());
    	List<List<int[]>> list = new ArrayList<>();

    	for(int i = 0; i < d; i++) {
    		list.add(new ArrayList<>());
    		list.get(i).add(new int[] {i + 1, 1});
    	}

    	int a, b, c;
    	for (int i = 0; i < n; i++) {
			stk = new StringTokenizer(br.readLine());
			a = stoi(stk.nextToken());
			b = stoi(stk.nextToken());
			c = stoi(stk.nextToken());

			if(b <= d)
				list.get(a).add(new int[] {b,c});
		}

    	// 다익 스트라

    	int[] node = new int[d + 1];
    	boolean[] vis = new boolean[d + 1];

    	int min, max_value = 99999;
    	Arrays.fill(node, max_value);
    	node[0] = 0;
    	int curN = -1;
    	while(true) {
    		min = max_value;

    		// 제일 작은 노드를 찾는다.
    		for(int i = 0; i < d; i++) {
    			if(node[i] < min && !vis[i]) {
    				min = node[i];
    				curN = i;
    			}
    		}

    		vis[curN] = true;
    		if(min == max_value) {
    			break;
    		}
    		// 현재 경유지에서, 다음 갈 수 있는 곳을 찾는다.
    		for(int[] nd : list.get(curN)) {
    			if(!vis[nd[0]] && node[nd[0]] > node[curN] + nd[1]) {
    				node[nd[0]] = node[curN] + nd[1];
    			}
    		}
    	}
    	System.out.println(node[d]);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}