[BJ1446] 지름길

 백준 - 지름길 

문제 링크

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

1446번: 지름길

 

문제 입출력

2 100
10 60 40
50 90 20

80

 

문제 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;


public class Main {
	static int ans, N, D;
	static int[] dp; // 점화식
	static List<Node> shortCuts = new ArrayList<>(); // 지름길 배열

	/*
	 점화식 dp[i]: 해당 i 위치에 도착했을 때의 가장 짧은 운전 거리 
	 dp[0] -> 0
	 dp[1] -> 1
	 ...
	 dp[49] -> 49
	 dp[50] -> 10 으로 갱신 
	 
	 dp[i] = dp[i+1] + 1
	 or
	 dp[i] = dp[s] + (new distance)
	 */


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken()); // 고속도로 길이

		// 초기화
		dp = new int[D + 1];

		for (int i = 0; i <= D; i++) dp[i] = i;

		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 dis = Integer.parseInt(st.nextToken());

			if (s > e) continue; // 역주행
			if (e - s > D) continue; // 지름길이 아닌 경우
			if (s < 0 || e > D) continue; // 범위 넘어가는 경우

			shortCuts.add(new Node(s, e, dis));
		}

		// Collections.sort(shortCuts,
		// (e1, e2) -> e1.s == e2.s ? (e1.e == e2.e ? e1.dis - e2.dis : e1.e - e2.e)
		// : e1.s - e2.s);

		// 탐색
		sol();

		// 출력
		ans = dp[D];
		System.out.println(ans);

	} // end main


	private static void sol() {
		for (int i = 1; i <= D; i++) {
			
			for (Node node : shortCuts) {
				if (i == node.e) { // 만약 지름길이 있는 경우 
					int ndis = dp[node.s] + node.dis;
					dp[i] = Math.min(dp[i], Math.min(dp[i - 1] + 1, ndis));
				} else dp[i] = Math.min(dp[i], dp[i - 1] + 1); // 지름길이 없는 경우 

			}

		}

	} // end sol


	static class Node {
		int s, e;
		int dis;


		public Node(int s, int e, int dis) {
			super();
			this.s = s;
			this.e = e;
			this.dis = dis;
		}


		@Override
		public String toString() {
			return "Node [s=" + s + ", e=" + e + ", dis=" + dis + "]";
		}

	} // end Node
}

맞왜틀 이었던 문제.. 알고보니 dp 배열을 초기화 할때 잘못된 값을 넣어서 발생하는 문제였다.

처음에 초기화로 D + 1 의 값을 넣었는데, 이때문에 dp[i - 1] + 1 과 비교할 시 오답이 발생한 것 같다.

D + 1 이 초기값이면 당연히 dp[i - 1] + 1 이 그보다 작기 때문에 값이 갱신된다.

하지만 사실 순차대로 1을 더해줬을 때가 d[i - 1] + 1 보다 값이 작을 수 있기에 문제가 발생한다.

아무튼간 풀어서 기분은 좋다. 다익스트라 라기보다는 보편적인 유형의 다이나믹프로그래밍 문제 인 것 같다. 

 

길을 돌면서 만약에 지름길이 있다면 (dp[i], dp[i-1] + 1, dp[s] + dis) 중에 min 값을 갱신해준다.

지름길이 없는 경우는 (dp[i], dp[i-1] + 1) 중에 min 값을 갱신해준다.

dp[i] 와 계속 비교하는 이유는 전체 shortCuts 배열을 돌기 때문이다.

동일한 시작 - 도착 위치의 지름길이 있을 수 있기 때문에 기존의 것과 비교해주어야 한다. 

 

 

 

 

 

 

 

 

 

#백준 지름길 java dp #백준 지름길 자바 dp #백준 지름길 다익스트라 #bj1446 지름길

---