[백준 JAVA] 1446번: 지름길

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

 

이 문제를 풀었을때 의식의 흐름과 첫번째 정답을 도출한 과정을 먼저 설명하고자 한다.

 

우선 조합으로 모든 지름길을 사용할 수 있는 경우의 수를 모두 따진 다음 가장 최소의 값을 출력하는게 가장 처음 떠오른 생각이였다. 

 

가장 시간이 많이 걸리기도 하고 N <= 12 였기 때문에 가능한 생각인거같아서 다른 방법도 생각해보았다.

 

두번째로는 다익스트라와 비슷한 방식으로 가장 길이를 많이 줄여주는 지름길을 먼저 택하는 방식이였는데 뭔가 반례가 무조건 있을꺼같았다.

 

세번째로 생각한 방법은 DP를 이용한 방법으로 dp[i][j]를 j지름길까지 고려했을 경우 i까지 갈 경우 최소시간을 생각했는데 이전에 사용한 지름길에 대한 정보를 줄 수 없으므로 겹치는 지름길을 판단하기 어렵다고 생각했다.

 

 

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

public class Main {
    public static int N, D, ans;
    public static int[][] road;
    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());
        road = new int[N][3];
        ans = D;
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            road[i][0] = Integer.parseInt(st.nextToken());
            road[i][1] = Integer.parseInt(st.nextToken());
            road[i][2] = Integer.parseInt(st.nextToken());
        }

        dfs(0, 0, new ArrayList<Integer>());

        System.out.println(ans);
    }
    public static void dfs(int at, int depth, List<Integer> list){
        if(depth == N){
//            for(int i = 0; i < list.size(); i++){
//                System.out.print(list.get(i));
//            }
//            System.out.println();
            int dis = toDistance(list);
            ans = Math.min(dis, ans);
            return;
        }
        for(int i = at; i < N; i++){
            // 1. 이제까지 왔던 길과 겹치지 않고 D를 넘지 않으면
            if(isOverlap(list, i)){
                // 2. 리스트에 추가 후 다음
                list.add(i);
                dfs(i + 1, depth + 1, list);
                for(int j = 0; j < list.size(); j++){
                    if(list.get(j) == i){
                        list.remove(j);
                        break;
                    }
                }
            }
            dfs(i + 1, depth + 1, list);
        }
    }
    public static int toDistance(List<Integer> list){
        int dis = D;
        for(int cur : list){
            int from = road[cur][0];
            int to = road[cur][1];
            int value = road[cur][2];
            dis = dis - (to - from) + value;
        }

        return dis;
    }
    public static boolean isOverlap(List<Integer> list, int now){
        int from = road[now][0];
        int to = road[now][1];

        if(to > D) return false;

        for(int cur : list){
            int fromC = road[cur][0];
            int toC = road[cur][1];

            if(toC > D) return false;

            if(to <= fromC || toC <= from) continue;
            else return false;
        }

        return true;
    }
}

 

 

앞에서는 이 문제를 풀기 위해 DFS로 가능한 모든 지름길 조합을 탐색하는 방식을 선택했다.

N ≤ 12라는 조건 때문에 완전탐색도 충분히 가능했고, 실제로 정답도 맞았다.

 

하지만 문제를 다시 보면서 몇 가지 찜찜한 점들이 있었다.

 

찜찜했던 이유는

1. 지름길 겹침 여부를 직접 판단해야 한다.
   isOverlap(), List add/remove, toDistance() 등의 부가적인 로직이 많이 필요했다.
2. 본질적으로 “지름길 조합 문제”처럼 보이지만, 사실은 “최단 거리 문제”라는 느낌이 들었다.
3. 더 나은 방향이 있을 것 같았다.
   DFS는 맞긴 맞는데, 뭔가 문제의 구조를 완전히 활용하지 못하고 힘으로 밀어붙이는 느낌이 들었다.

 

 

도로는 0km부터 Dkm까지 ‘직선’이다.

 

그리고 지름길은 이 직선 위의 특정 지점에서 특정 지점으로 가는 특수한 간선일 뿐이다.

 

즉,
0 ~ D까지 순서대로 진행하는 선형 그래프 + 중간에 몇 개의 추가 간선이 있는 DAG 구조다.

그러니 이 문제는 사실 이렇게 다시 정의된다.

 

0에서 D까지 가는 최소 비용을 구하는 최단거리 문제

 

여기서 중요한 건

“어떤 지름길 조합을 썼는지”가 아니라

“각 지점까지 최소 몇 km를 썼는지” 뿐이다.

 

 

 

DP 정의

dp[x] = 0에서 x 지점까지 이동하는 데 필요한 최소 거리

초기값: dp[0] = 0 나머지 dp[i] = 매우 큰 수

 

점화식

각 위치 i에서 선택할 수 있는 행동은 두 가지다.

 

1. 직선으로 한 칸 이동

dp[i+1] = min(dp[i+1], dp[i] + 1)

 

2. i에서 시작하는 모든 지름길 사용

지름길이 (i → end, cost)라면

dp[end] = min(dp[end], dp[i] + cost)

 

같이 고려했던 점

• end > D이면 지름길은 무시한다.
• to - from ≤ dist인 비효율적인 지름길도 무시해도 된다.

 

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

public class Main {
    public static int N, D;
    public static int[] dp;
    public static List<int[]> list;
    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());
        list = new ArrayList<>();

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            if(v - u < w || v > D) continue;
            list.add(new int[] {u, v, w});
        }
        list.sort((o1, o2) -> Integer.compare(o1[0], o2[0]));

        int cnt = 0;
        dp = new int[D + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 0; i < D; i++){
            dp[i + 1] = Math.min(dp[i + 1], dp[i] + 1);
            for(int j = cnt; j < list.size(); j++){
                int[] cur = list.get(j);
                if(cur[0] == i && dp[cur[1]] > dp[i] + cur[2]){
                    dp[cur[1]] = dp[i] + cur[2];
                    cnt++;
                }
            }
        }

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

 

 

풀 수 있는것도 중요하지만 문제의 본질을 좀 더 살펴보고 문제를 풀어보자.