[JAVA] 백준 1446 - 지름길

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

다익스트라를 풀고 싶어서 Solved.ac에서 다익스트라 태그를 붙여서 찾은 문제이다.

다익스트라 태그를 타고 들어갔기 때문에 문제를 보고 바로 그리디하게 정렬할 수 있는 기준을 열심히 찾았는데

아무리 봐도 그 기준이 모호했다. 하나를 고치면 다른 곳에서 구멍이 났다.

그래서 N도 작겠다 그냥 DFS로 풀었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        int roadCount = info[0];
        int targetLocation = info[1];
        List<R1446> roadList = new ArrayList<>();
        for (int i = 0; i < roadCount; i++) {
            int[] road = getArray(br.readLine());
            if(road[1]<=targetLocation && road[1] - road[0] > road[2] ) roadList.add(new R1446(road[0],road[1],road[2]));
        }
        Collections.sort(roadList);
        dfs(targetLocation,0,0, roadList, new boolean[roadCount+1]);
        System.out.println(min);
    }

    static void dfs(int targetLocation, int curLocation, int weight, List<R1446> roadList, boolean[] visited){
        min = Math.min(min, targetLocation - curLocation +weight);
        for (int i = 0; i < roadList.size(); i++) {
            if(visited[i]) continue;
            R1446 road = roadList.get(i);
            if(road.start<curLocation) continue;
            visited[i] = true;
            dfs(targetLocation,road.end, weight + road.weight + (road.start - curLocation) ,roadList,visited);
            visited[i] = false;
        }
    }
    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class R1446 implements Comparable<R1446>{
    int start;
    int end;
    int weight;
    R1446(int s,int e, int w){
        this.start = s;
        this.end = e;
        this.weight = w;
    }
    @Override
    public int compareTo(R1446 road){
        int s= this.start -road.start;
        if(s==0) return this.weight - road.weight;
        return s;
    }
}