[백준] 지름길 - 자바(Java)

문제 링크

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

문제 설명

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

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

입력

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

출력

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

 

문제 풀이

[고려사항]

지름길로 가는 거리와 아닌 거리의 합을 구하면서, 모든 조합 중 가장 짧은 거리를 찾아야한다.

여기서 지름길은 원래 거리보다 짧은 거리여야하고, 지름길 여러개가 범위가 겹치면 더 짧은 거리의 지름길을 선택해야한다.

이런 식으로 지름길을 선택하고 최단 거리를 고려해서 구현하려고하면 구현이 복잡해져서 예외처리를 제대로 하지 못할 수 있다.

그래서 이 문제는 DP(Dynamic Programming)로 풀어야 한다.

[알고리즘, 구현방법]

DP로 모든 거리(0 ~ D)의 지점을 방문해서 해당 거리에서의 최단 거리를 저장한다.

즉, dp[i] = i meter 까지의 최단 거리를 의미한다.

 

그리고 지름길의 도착 위치에서는 지름길 시작 위치 ~ 도착 위치까지의 거리와 이전 위치 + 1 중에 최솟값을 할당해야한다.

즉, 현재 지점까지의 최단 거리 = min(이전 지점까지의 최단 거리 + 1, 지름길 최단 거리(=지름길 시작 지점까지의 최단 거리 + 지름길 거리)로 계산해야한다.

 

지름길의 시작 위치를 s, 지름길 길이가 distance라고 한다면, (i = 현재 거리 = 지름길의 도착 위치)

dp[i] = MIN(dp[i-1] + 1, dp[s] + distance) 가 된다.

 

[지름길 정보 저장 방식]

지름길에 대한 정보를 가지고 있다가 0 ~ D거리를 방문하면서 지름길의 도착 위치에 도달했는지를 확인할 수 있어야한다.

dp[i]를 할당할때, 지름길의 도착 위치라면 지름길 거리를 반영해서 최솟값을 계산해야하기 때문이다.

그래서 지름길 정보를 Map<(도착 위치), (지름길 정보)>로 저장했다. Key를 도착 위치로 해두면 dp[i] 값을 할당할 때 현재 위치(i)가 Key값으로 포함되어있는지를 확인하여 지름길 여부를 판단할 수 있기 때문이다.

 

그리고 지름길의 도착 위치가 2개 이상인 경우도 있기 때문에, 도착 위치(Key)에 매핑되는 지름길 정보를 List로 저장했다.

Map<Integer, List<Shortcut>> shortcutInfo = new HashMap<>();

[풀이 과정]

1. 지름길 정보 저장

• 도착 위치가 고속도로 길이를 초과하면 저장 안함
• 끝 지점 - 시작 지점이 지름길 거리보다 짧으면 저장 안함 (즉, 지름길 거리가 짧은 경우에만 저장)
• 지름길 도착 위치가 2개 이상인 경우, 저장된 리스트에 지름길 정보 추가
• 지름길 도착 위치에 대해 저장된 지름길 정보가 없다면, 새로 리스트에 지름길 정보 추가

2. dp 배열에 각 위치별 최단 거리를 저장

• 현재 위치에 지름길 정보가 있다면 (=도착 위치 정보가 있다면 =Map의 containsKey가 true라면), 지름길 정보 계산
  • 도착 위치까지의 지름길 정보가 여러개인 경우가 있기때문에 해당 위치에서의 지름길 리스트를 반복하면서 최단 거리 갱신
    • 지름길 거리를 포함한 현재 위치에서의 거리 = 시작 지점까지의 최단 거리 + 해당 지름길 거리
• 현재 위치에서의 최단 거리 할당
  • 현재 지점까지의 최단 거리 = min(이전 지점까지의 최단 거리 + 1, 지름길 최단 거리(=지름길 시작 지점까지의 최단거리 + 지름길 거리)

3. dp[D] 출력

 

정답 코드

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

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

        Map<Integer, List<Shortcut>> shortcutInfo = new HashMap<>();
        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) continue;
            // 끝 지점 - 시작 지점이 지름길 거리보다 짧으면 저장 안함 (즉, 지름길 거리가 짧은 경우에만 저장)
            if (e - s <= d) continue;

            // 지름길 정보 세팅
            Shortcut sc = new Shortcut(s, e, d);
            List<Shortcut> list = new ArrayList<>();
            // 이미 도착 지점 지름길 정보가 있으면, 저장된 리스트 정보에 추가해야됨
            if (shortcutInfo.containsKey(e)) list = shortcutInfo.get(e);

            list.add(sc);
            shortcutInfo.put(e, list);
        }

        int[] dp = new int[D + 1];
        dp[1] = 1;
        for (int i = 1; i <= D; i++) {
            int min = D;
            if (shortcutInfo.containsKey(i)) { // 지름길 루트가 있는 경우
                int val = 0;
                for (Shortcut s: shortcutInfo.get(i)) { // 도착 지점까지의 지름길이 여러개인 경우를 위한 반복문
                    val = dp[s.start] + s.distance; // 시작 지점까지의 최단 거리 + 해당 지름길 거리
                    if (val < min) min = val; // 도착 지점까지의 지름길 중 최솟값 갱신
                }
            }
            // 현재 지점까지의 최단 거리 = min(이전 지점까지의 최단 거리 + 1, 지름길 최단 거리(=지름길 시작 지점까지의 최단 거리 + 지름길 거리)
            dp[i] = Math.min(dp[i-1] + 1, min); // 해당 지점까지의 최단 거리 계산
        }
        System.out.println(dp[D]);
    }

    public static class Shortcut {
        int start;
        int end;
        int distance;

        public Shortcut(int start, int end, int distance) {
            this.start = start;
            this.end = end;
            this.distance = distance;
        }
    }
}