[백준] 1446. 지름길(Java)

[BOJ] 1446. 지름길

📌 풀이 과정

1. 기본 경로 설정

고속도로는 지름길이 없을 때, 1km씩 이동하는 기본 경로를 설정해야 한다.
고속도로는 기본적으로 매 구간마다 1km씩 이동하는 경로로 이루어져 있다. 지름길이 없는 경우에는 단순히 고속도로를 따라 1km씩 이동해야 하므로, 기본 경로를 1km로 설정하여 지름길과 비교할 수 있는 기준을 만들어야 한다.

2. 지름길 추가

각 지름길은 문제에서 주어진 정보에 따라 그래프에 추가한다.
단, 지름길의 종료 지점이 고속도로의 길이보다 큰 지름길은 추가하지 않는다.

이처럼 고속도로의 기본 경로에 대한 조건을 추가한 후, 다익스트라 알고리즘을 구현하면 된다.

✨ 제출 코드

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

/**
 * 1446. 지름길
 * 메모리 : 14436 KB
 * 시간 : 108 ms
 */
public class Main {

    static int N, D;
    static int[] distance;
    static ArrayList<Node>[] graph;

    static class Node{
        int v;
        int dist;

        public Node(int v, int dist) {
            this.v = v;
            this.dist = dist;
        }
    }

    public static void dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>((a,b) -> a.dist - b.dist);
        pq.add(new Node(start,0));

        while(!pq.isEmpty()){
            Node cur = pq.poll();
            int curNode = cur.v;
            int curDist = cur.dist;

            if(distance[curNode] < curDist) continue;

            for(Node next : graph[curNode]){
                int newDist = distance[curNode] + next.dist;
                if(newDist < distance[next.v]){
                    distance[next.v] = newDist;
                    pq.add(new Node(next.v, newDist));
                }
            }

        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 지름질의 개수
        D = Integer.parseInt(st.nextToken()); // 고속도로의 길이

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

        distance = new int[D + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[0] = 0;

        // 고속도로의 기본 경로 (1km씩 이동하는 경로)
        for(int i = 0; i < D; i++) {
            graph[i].add(new Node(i + 1, 1));
        }

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            if(b <= D){
                graph[a].add(new Node(b, cost)); // 지름길 추가
            }
        }

        dijkstra(0);
        System.out.println(distance[D]);
    }
}

---

DP로 풀이한 사람들도 많던데 익숙해지면 DP로도 다시 풀어보자!