백준 1446[자바] java 지름길

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

1446번: 지름길

▶문제

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

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

▶입력

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

▶출력

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

▶해설

DP로만 풀수 있을줄 알았는데 N,D의 값이 작아서 DFS를 이용해서 풀 수 있는 문제입니다. 조건을 살펴보겠습니다.

 

1. 고속도로의 끝에 딱 맞춰서 끝나야한다. (ex 150이라면 150에 맞춰서 끝나야됨)

2. 지름길 시작지점에서만 진입할 수 있다. 

 

저는 DFS로 접근해보겠습니다. 

 

DFS로 접근하기 위해서는 3가지의 분기점이 있습니다.

 

1. 지금까지 온 길이 고속도로의 끝을 넘었을 때

2. 지금까지 온 길이 고속도로의 끝과 딱 맞을때

3. 지금까지 온 길이 고속도로의 끝보다 작을 때

 

1번: DFS를 아무런 조치하지 않고 종료하면됩니다. 

if(now>end){
    return;
}

 

2번: 지금까지 이동한 거리와 기록중에 최소값을 구해주면 됩니다. 

else if(now==end){
    result= Math.min(result,distance);
    return;
}

 

3번: (고속도로의 끝지점 - 지금까지 온 길) + 지금까지 이동한 거리와 기록을 비교해줍니다. 

이 경우는 현재 조건을 만족하는 지름길이 없거나, 지름길을 선택하지 않았을 때 끝지점까지 이동하는 거리를 구하는 것입니다. 따라서 지름길을 이후에 선택할 수도 있기 때문에 DFS를 종료하지 않습니다. 

else{
    result = Math.min(result, distance+(end-now));
}

 

이제 지름길을 방문했는지 따져보고, 지름길의 시작지점이 내가 현재 있는 위치와 같은지 판단합니다. 조건에 부합할 경우 지름길의 끝을 우리가 앞으로 시작할 지점으로 넣고, 지나온 거리에 지름길의 값을 넣어줍니다. 만약 지름길을 선택하지 않았다면, 현재 위치+1, 지금까지 지나온 거리+1 을 해주므로써 1거리 만큼 간 것을 다음 DFS로 넘겨줍니다. 

for(int i=0; i<paths.size(); i++){
    if(!check[i]){
        Path path = paths.get(i);
        if(path.start==now){
            check[i]=true;
            dfs(path.end, m, distance+ path.cost);
            check[i]=false;
        }
    }
}
dfs(now+1, m, distance+1);

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Path{
    int start;
    int end;
    int cost;
 
    public Path(int start, int end, int cost) {
        this.start = start;
        this.end = end;
        this.cost = cost;
    }
}
 
 
public class Main {
 
 
    static List<Path> paths;
    static int n,m;
    static int result = Integer.MAX_VALUE;
    static boolean [] check;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
 
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
 
 
        paths = new ArrayList<>();
 
        int start,end, cost;
 
        for(int i=0; i<n; i++){
            String[] s1 = br.readLine().split(" ");
            start = Integer.parseInt(s1[0]);
            end = Integer.parseInt(s1[1]);
            cost = Integer.parseInt(s1[2]);
            if(start>m || end>m){
                continue;
            }
            paths.add(new Path(start,end,cost));
        }
 
        check = new boolean[paths.size()];
        dfs(0,m,0);
 
        System.out.println(result);
    }
 
    private static void dfs(int now, int end, int distance){
        if(now>end){
            return;
        }
        else if(now==end){
            result= Math.min(result,distance);
            return;
        }
        else{
            result = Math.min(result, distance+(end-now));
        }
 
        for(int i=0; i<paths.size(); i++){
            if(!check[i]){
                Path path = paths.get(i);
                if(path.start==now){
                    check[i]=true;
                    dfs(path.end, m, distance+ path.cost);
                    check[i]=false;
                }
            }
        }
        dfs(now+1, m, distance+1);
 
    }
}