[Baekjoon] 1446_지름길

Silver I

문제(출처: https://www.acmicpc.net/problem/1446)

---

< 지름길 >

 

문제 풀이 

 

지름길을 ArrayLIst에 저장한 후 모든 길을 탐색하면서 지름길로 이동 가능하면 이동 후 최솟값을 찾는다.

 

 

 my solution (Java)

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

public class _1446_ { // 지름길

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());

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

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int num = Integer.parseInt(st.nextToken());
			if (start > d || end > d) {
				continue;
			}
			list.get(start).add(new int[] { end, num });
		}

		for (int i = 0; i < d + 1; i++) {
			for (int j = 0; j < list.get(i).size(); j++) {
				int temp[] = list.get(i).get(j);

				if (arr[temp[0]] > arr[i] + temp[1]) {
					arr[temp[0]] = arr[i] + temp[1];
					for (int k = temp[0]; k < d + 1; k++) {
						if (arr[k] > arr[temp[0]] + (k - temp[0])) {
							arr[k] = arr[temp[0]] + (k - temp[0]);
						}
					}
				}
			}
		}

		System.out.println(arr[d]);
	}
}

변수)
n, d : 지름길 개수, 고속도로 길이
arr : 거리의 최솟값
list : 지름길
start, end, num : 지름길의 시작 위치, 도착 위치, 지름길의 길이

 

arr 배열에 각 거리를 저장하고 list에는 지름길을 저장하기 위해 초기화한다. 지름길을 n개 입력받은 후 list에 저장한다.

arr 배열을 전체 탐색하면서 지름길이 있는지 확인한다. 지름길이 있다면 지름길로 이동하는 것이 최솟값인지 확인 후 최솟값이라면 값을 업데이트한다. 그 후 남은 거리들도 최솟값으로 업데이트한다.

 

최종 운전해야 하는 거리의 최솟값인 arr 배열의 마지막 값을 출력한다.

---

---