[백준 1446] 지름길(Java)

문제 링크 : https://www.acmicpc.net/problem/1446

이 문제는 다익스트라를 이용해서 풀 수 있습니다. 단 일반적인 다익스트라 방식과는 달리 약간의 변형이 필요합니다.

이 문제는 모든 경로를 하나씩 밟아가기 때문에 지름길만을 연결한다고 문제를 풀 수 없습니다. 따라서 모든 지점을 1씩 증가시키면서 각 지점에서 지름길 여부에 따라 다익스트라를 진행하는 방식으로 풀어야 합니다. 즉 기존의 우선 순위 큐에 저장하여 체크 배열을 통해 검토하는 것이 아니라, 시작값을 계속 증가시키면서 현재 시작값에서 존재하는 지름길 정보에 따라 시작값을 최신화시켜주어야 합니다.

다음은 코드입니다.

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

class Main{
    static int N,D;
    static List<List<Node>> graph = new ArrayList<>();
    static int[] distance;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        for(int i=0;i<=10001;i++) graph.add(new ArrayList<>());
        distance = new int[10001];
        for(int i=0;i<distance.length;i++) distance[i] = i;

        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 w = Integer.parseInt(st.nextToken());
            graph.get(a).add(new Node(b,w));
        }

        dijkstra(0);

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

    static void dijkstra(int start){
        if(start>D) return;

        if(distance[start+1] > distance[start] + 1) distance[start+1] = distance[start]+1;

        for(int i=0;i<graph.get(start).size();i++){
            if(distance[start]+graph.get(start).get(i).weight < distance[graph.get(start).get(i).node])
                distance[graph.get(start).get(i).node] = distance[start]+graph.get(start).get(i).weight;
        }

        dijkstra(start+1);
    }

    static class Node {
        int node;
        int weight;

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