[백준] 지름길 1446번 (🥈실버1)

사이트

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

 

문제

분석

서론

문제 이해는 어렵지가 않았다. 이 문제가 왜 DP 유형인지 좀 의아했다.

필자는 dfs 즉 재귀함수를 이용해서 풀었다. 

 

본론

일단 먼저 첫번째!! 필자는 걸러주었다.

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

 

즉 입력을 위와 같이 받을시 가정을 해보겠다. 

 

지름길 갯수가 5 이고, 고속도로의 길이는 150이다.

 

이때 첫번째 지름길을 보면 시작지점은  0, 도착지점은 50 마지막으로 지름길 길이는 10이다!

즉 일반길로 가면 50인데 지름길을 사용하니깐 거리가 10이 나온것이다.

 

하지만 문제의 조건을 보면 역주행은 불가능하다고 나와있다.

즉 네번째 지름길 100 151 10 은 151때문에 지름길 이용이 불가능 한것이다.

 

추가로 다섯번째 즉 마지막 지름길 110 140 90은 일반으로 30으로 갈 수있는데 이것보다 더 길다...... 

 

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 c = Integer.parseInt(st.nextToken());

    if (b <= d && b - a >= c) {
        road[i][0] = a;
        road[i][1] = b;
        road[i][2] = c;
        max = Math.max(a, max);
    } else {
        road[i][0] = 10001;
        road[i][1] = 10001;
        road[i][2] = 10001;
    }


}

 

그래서 필자는 두 조건을 이용해 먼저 걸러냈다. 

즉 위와 같이 입력을 받을때 조건이 포함되지 않을때 10001로 값을 할당했다.

왜냐하면 고속도로 제한길이는 10000이라고 문제에 나와있어서 이다.  

 

max = Math.max(a, max);

 

추가로 이 코드는 시작지점이 마지막 지점보다  작을때를 위함이다. 아래에 자세히 설명!! 

 

private static void solution(int level, int end) {
    if (end > max) {
        final_length = d - end;
        length += final_length;

        min = Math.min(length, min);

        return;
    }
    for (int i = 0; i < n; i++) {
        if (road[i][0] >= end && road[i][0] != 10001 && road[i][1] != 10001 && road[i][2] != 10001) {
            int start = road[i][0];
            length += (start - end);

            length += road[i][2];
            solution(level + 1, road[i][1]);

            length -= (road[i][2] + (start - end) + final_length);
            final_length = 0;

        }
    }


}

 

핵심 코드이다. 차근차근 보자 

for (int i = 0; i < n; i++) {
    if (road[i][0] >= end && road[i][0] != 10001 && road[i][1] != 10001 && road[i][2] != 10001) {
        int start = road[i][0];
        length += (start - end);

        length += road[i][2];
        solution(level + 1, road[i][1]);

        length -= (road[i][2] + (start - end) + final_length);
        final_length = 0;

    }
}

 

이 코드는 먼저 기존 조건에 벗어나 10001을 포함시키지 않기 위해 if문을 다음과 같이 넣었고

추가로 road[i][0] >=0 end 는 시작점이 이전에 도착지점보다 크거나 같을때를 의미한다. 그래야지 이을 수 있으니깐!

 

int start = road[i][0];
length += (start - end);

length += road[i][2];
solution(level + 1, road[i][1]);

length -= (road[i][2] + (start - end) + final_length);
final_length = 0;

 

그럼 이 부분에서 첫번째 문단은 

이전 도착지점과 시작지점을 빼서 더해야 된다!! 

 

solution(0, 0);

 

자 왜냐하면 이 함수 호출을 이렇게 했다 즉 end 가 0이다! 

이때 첫번째 입력 지름길이 0 50 10이 아니라 예를 들어서 10 50 10일때는 

10까지는 일반으로 가야된다. 그래서 저렇게 해준것이다. 

 

int start = road[i][0];
length += (start - end);

length += road[i][2];
solution(level + 1, road[i][1]);

length -= (road[i][2] + (start - end) + final_length);
final_length = 0;

 

그럼 다시 여기서 두번째 문단은 이젠 지름길 길이를 더해주고 재귀함수를 이용해서 level, 도착지점을 호출한다.

 

if (end > max) {
    final_length = d - end;
    length += final_length;

    min = Math.min(length, min);

    return;
}

 

여기서 end가 max 보다 클때 즉 max가 시작지점이므로 50이고 end가 100 일때

이젠 시작점이 100이 없으므로 즉 지름길 이동을 못하고 일반 고속도로를 이용해야 된다.

그래서 위와 같이 하고 최종 단계 이므로 즉 재귀함수의 마지막 단계이므로 위와같이 Math.min을 이용해서 최소거리를 더해주었다. 

 

 

length -= (road[i][2] + (start - end) + final_length);
final_length = 0;

 

여기서는 return이 됐으면 이전에서 더해준것을 빼주어야된다. 그래야지 트리처럼 다음 단계로 갈 수 있으니깐!! 

 

 

그래서 이런식으로 해주면 해결이다!! 

 

if(min == Integer.MAX_VALUE){
    System.out.println(d);
}else {
    System.out.println(min);
}

 

정답을 출력할때 지름길이 없을 경우도 있으니깐 위와 같이 조건을 걸어두어야 된다. 

 

 

전체코드

package dp;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class DP1446 {
    static int d;

    static int n;

    static int[][] road;

    static int min = Integer.MAX_VALUE;

    static int max = 0;

    static int length;

    static int final_length = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

        road = new int[n][3];

        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 c = Integer.parseInt(st.nextToken());

            if (b <= d && b - a >= c) {
                road[i][0] = a;
                road[i][1] = b;
                road[i][2] = c;
                max = Math.max(a, max);
            } else {
                road[i][0] = 10001;
                road[i][1] = 10001;
                road[i][2] = 10001;
            }


        }


        solution(0, 0);
        if(min == Integer.MAX_VALUE){
            System.out.println(d);
        }else {
            System.out.println(min);
        }
    }

    private static void solution(int level, int end) {
        if (end > max) {
            final_length = d - end;
            length += final_length;

            min = Math.min(length, min);

            return;
        }
        for (int i = 0; i < n; i++) {
            if (road[i][0] >= end && road[i][0] != 10001 && road[i][1] != 10001 && road[i][2] != 10001) {
                int start = road[i][0];
                length += (start - end);

                length += road[i][2];
                solution(level + 1, road[i][1]);

                length -= (road[i][2] + (start - end) + final_length);
                final_length = 0;

            }
        }


    }
}

결과

느낀점

지름길이 없을때를 생각 못해서 20분 날림.... 이것만 아니면 쉬운 문제였는데 아쉽다!!

다이스트라, dp 라고 해서 겁먹었는데...  재귀 함수로 풀어도 되는 쉬운 문제 였다.