[1446] 지름길 (JAVA)

# 문제 설명

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

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

---

입력

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

---

출력

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

 

# 정답 코드

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()); //고속도로의 길이

        ArrayList<Node>[] graph = new ArrayList[10001]; //인접 리스트
        for (int i = 0; i <= 10000; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int n = 0; n < N; n++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight= Integer.parseInt(st.nextToken());

            graph[start].add(new Node(end, weight));
        }

        int[] distance = new int[10001]; //최단 거리 배열
        for (int i = 0; i <= 10000; i++) {
            distance[i] = i;
        }

        int now = 0; //현재 위치
        while (now < D) {
            distance[now + 1] = Math.min(distance[now] + 1, distance[now + 1]);

            for (Node i : graph[now]) {
                distance[i.node] = Math.min(distance[now] + i.weight, distance[i.node]);
            }

            now++;
        }

        System.out.print(distance[D]);
    }

    public static class Node {
        int node;
        int weight;

        Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }
}

 

고속도로 길이의 범위가 0~10000이므로 각 위치를 노드로 하여 10001개의 노드가 있다.

인접 리스트와 최단 거리 배열을 10001개로 생성한다.

최단 거리 배열은 현재 위치 0에서 특정 위치 n까지 지름길 없이 가는데 n만큼 걸리므로 이에 맞춰 초기화한다.

 

다익스트라를 이용하여 0부터 D까지의 최단 거리를 구한다.

현재 위치가 D보다 작을 때까지만 반복한다.

• distance[now+1]와 distance[now]+1 중 작은 값을 distance[now+1]로 설정한다.
• now에 연결된 모든 노드에 다음과 같은 연산을 수행한다.
  (선택 노드 최단 거리 값 + 에지 가중치)와 연결 노드 최단 거리 값 중 작은 값을 distance[i.node]로 설정한다.