[BOJ] 1446 : 지름길 (JAVA)

백준 1446번: 지름길

 

풀이

 

DP를 이용해서 풀었다.

우선 map에 지름길을 이용하지 않고 갈 때 걸리는 시간을 담아준다.(map[i] = i)

 

그리고 지름길을 road 배열에 담아준 뒤,

 

0부터 도착지점까지의 최소시간을 체크해주기 위해

만약 i지점에 지름길 도착지점이 있으면, 비교를 해주면 된다.

Math.min(지름길을 이용하지 않고 갈 때 걸리는 시간인 map[i], 지름길 시작점까지 걸린 시간+지름길 이용 시간)

그럼 지름길 도착지점에서 최소시간으로 갱신이 가능하다.

 

i+1지점에서 최소시간으로 갱신한 값이 더 적은지 확인을 해줘야하기 때문에

Math.min(지름길을 이용하지 않고 갈 때 걸리는 시간인 map[i], 갱신됐을 수 있는 map[i-1]에 +1한 값)

을 해주면 된다 !!

 

전체코드

package 백준renew;

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

public class 실버1_1446_지름길 {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int D = Integer.parseInt(st.nextToken());
		
		int map[] = new int[D+1];
		for(int i=0; i<D+1; i++) {
			map[i] = i;
		}
		
		int road[][] = new int[N][3];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			road[i][0] = Integer.parseInt(st.nextToken());
			road[i][1] = Integer.parseInt(st.nextToken());
			road[i][2] = Integer.parseInt(st.nextToken());
		}
		
		for(int i=1; i<D+1; i++) {
			map[i] = Math.min(map[i], map[i-1]+1);
			for(int j=0; j<N; j++) {
				if(road[j][1] == i) {
					map[i] = Math.min(map[i], map[road[j][0]]+road[j][2]);
				}
			}
		}
		
		sb.append(map[D]);
		bw.append(sb.toString());
		bw.close();
	}
}