[Java] 백준 1446 지름길

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

난이도

실버1

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

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());

		ArrayList<int[]> shortcuts = new ArrayList<>();
		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 d = Integer.parseInt(st.nextToken());
			if (e <= D) {
				shortcuts.add(new int[] { s, e, d });
			}
		}

		int[] dp = new int[D + 1];
		for (int i = 0; i < D + 1; i++) {
			dp[i] = i;
		}

		for (int i = 0; i <= D; i++) {
			if (i > 0) {
				dp[i] = Math.min(dp[i], dp[i - 1] + 1);
			}
			for (int[] s : shortcuts) {
				if (i == s[0]) {
					dp[s[1]] = Math.min(dp[s[1]], dp[i] + s[2]);
				}
			}
		}
		System.out.println(dp[D]);
	}
}

우선 문제에서 주어진 정보를 잘 저장하고, 지름길에 대한 정보도 int[]로 ArrayList에 저장하였다.

그리고 나서 최단 거리를 저장하기 위한 int[] dp를 선언하고 각 위치를 for문을 통해서 돌아가면서 인덱스 값에 맞춰 저장을 하였다.

그리고 0번 부터 목표 지점인 D까지 돌면서 현재 위치와 앞 위치에서 + 1 것들 중 최소값을 갱신해서 나아가면 된다.

그리고 지름길 목록을 돌아가면서 지름길을 갈 수 있는지 확인을 하고, 갈 수 있다면 지름길을 통해서 도착한 위치의 값을 지름길 도착 위치의 기본 길이와 현재 위치 + 지름길로 가는 길이를 비교하여 더 작은 값으로 갱신해주면 된다.