백준 1446번 - 지름길

문제

백준 1446번 - 지름길

아이디어

• 처음에는 거리만큼 그대로 dist 배열의 각 인덱스를 초기화해준다.
• N개의 지름길 정보를 저장하고, 0 ~ D까지 DP 방식으로 최솟값을 갱신해간다.
• 가중치가 모두 1이기 때문에 이전 거리에서 1을 더한 값만 비교하고, 연결된 지름길이 있으면 도착 위치의 최소 거리를 갱신해준다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(D)

코드 구현

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

public class BJ_1446 {

    static int[] dist;
    static ArrayList<Node>[] graph;

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

        dist = new int[d + 1];
        graph = new ArrayList[d + 1];

        for (int i = 0; i <= d; i++) {
            dist[i] = i;
            graph[i] = new ArrayList<>();
        }

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

            if (e <= d) {
                graph[s].add(new Node(e, w));
            }
        }

        for (int i = 0; i < d; i++) {

            if (dist[i + 1] > dist[i] + 1) {
                dist[i + 1] = dist[i] + 1;
            }

            for (Node adj : graph[i]) {
                if (dist[adj.to] > dist[i] + adj.w) {
                    dist[adj.to] = dist[i] + adj.w;
                }
            }
        }

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

    static class Node {
        int to, w;

        public Node(int to, int w) {
            this.to = to;
            this.w = w;
        }
    }
}