[Java] 백준 1446번: 지름길

[문제 바로 가기] - 지름길

💡 일단 생각하기!

DP로도, 다익스트라로도 풀 수 있는 문제!

나는 DP로 풀이했는데 다익스트라로 푸는 것보다 더 간단하다.
먼저 D + 1 크기의 dp 배열을 만들어준다. 0번째 인덱스 값을 빼고는 다 Integer.MAX_VALUE로 만들어주고 1부터 D까지 for문을 돌린다.

만약 해당 위치에 도착하는 지름길이 있을 경우 기존 길이과 직전의 길이+1, 지름길을 통해 왔을 때 걸리는 길이 중 가장 작은 값을 넣어준다.
지름길이 없는 경우엔 그냥 기존 길이와 직전의 길이+1 중 작은 값을 넣어준다.

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 백준 1446번 지름길
 * - dp로 풀이
 * - 범위가 크지 않기 때문에 D*N동안 최소값을 구해가면서 D의 값을 구한다
 * 
 * 메모리 : 11676kb 시간 : 68ms
 */

public class Main {
	public static void main(String[] args) throws Exception {
		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()); // 고속도로 길이
		int shortcut[][] = new int[N][3]; // 지름길 정보
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < 3; j++) {
				shortcut[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int dp[] = new int[D + 1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		
		for (int i = 1; i <= D; i++) {
			for (int j = 0; j < N; j++) {
				// 해당 위치로 도착하는 지름길이 있을 경우
				if (shortcut[j][1] == i) {
					dp[i] = Math.min(dp[i], Math.min(dp[i - 1] + 1, dp[shortcut[j][0]] + shortcut[j][2]));
				} else { // 없을 경우
					dp[i] = Math.min(dp[i], dp[i - 1] + 1);
				}
			}
		}
		
		System.out.println(dp[D]);
	}
}