백준 2157번 : 여행 [자바]

 

 

 

🧫 문제 분석

✔️ 출처

여행 골드 4

📖 문제

 

문제를 읽어보면 최단경로 다익스트라를 좀 변형해서 최장경로로 풀면 되지 않을가 싶은 생각이 들었는데

문제에서 'M개 이하의 도시를 지나는' 조건이 있기에 좀 어려울 것 같다는 생각이 들었다.

 

따라서 DP로 풀었다.

N번 도시까지 오는데 M개의 도시를 지나 먹은 기내식 최대 값을 구한다.

 

1 -> 3 10         3번 도시까지 오는데 2개의 도시를 지나 먹은 기내식 최댓값은 10

1 -> 2 5           2번 도시까지 오는데 2개의 도시를 지나 먹은 기내식 최댓값은 5

2 -> 3 3          이전에 2번 도시를 방문한 적이 있는지 확인,

                       1->2로 방문한 적이 있으므로 2번으로 오는데 먹은 기내식 최댓값 + 현재 기내식값 3

 

이런식으로 진행한다.

중요한 점은 방문을 순차적으로 할 필요가 있다. 1 -> 1~N , 2 -> 2~N, 3 ->  3~N

 

점화식

// a -> b로 가는 비행기, c의 기내식 점수 , j = 1~M-1 까지 해당 도시에 몇번째 방문인지
dp[b][j] = Math.max(dp[b][j+1], dp[a][j] + arr[a][b])    (dp[a][j] != -1) // 출발지의 j번째 방문한 적이 있다면

 

처음에는 우선순위 큐로 했는데 

굳이 그럴필요없이 배열로 하면 됐다. 

 

---

🔅 문제 풀이 [우선순위 큐]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1[0] != o2[0]) return o1[0] - o2[0];
            if (o1[1] != o2[1]) return o1[1] - o2[1];
            return o2[2] - o1[2];
        });

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dp[i], -1);
        }

        for (int i = 1; i <= m; i++) {
            dp[1][i] = 0;
        }

        for (int i = 1; i <= k; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            pq.add(new int[]{a, b, c});

        }

        while (!pq.isEmpty()) {

            int[] airPortInfo = pq.poll();
            int a = airPortInfo[0];
            int b = airPortInfo[1];
            int c = airPortInfo[2];

//            // a 도시를 방문하지 않았다면 방문처리, 자기 자신의 도시는 기내식 점수 0
//            if (dp[a][1] == -1) {
//                dp[a][1] = 0;
//            }

            // a 도시를 j번 째 지났다면 j번째의 기내식 최대값 + a->b로 가는 비행기의 기내식 값
            for (int j = 1; j <= m - 1; j++) {
                if (dp[a][j] != -1) {
                    dp[b][j + 1] = Math.max(dp[b][j + 1], dp[a][j] + c);
                }
            }
        }

        int max = 0;
        for (int i = 1; i <= m; i++) {
            max = Math.max(max, dp[n][i]);
        }

        System.out.println(max);

    }

}

 

🔅 문제 풀이 [배열]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n + 1][n + 1];
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dp[i], -1);
        }

        // 출발도시 1번도 m개의 개수안에 포함
        dp[1][1] = 0;

        for (int i = 1; i <= k; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            arr[a][b] = Math.max(arr[a][b], c);
        }

        for (int a = 1; a <= n; a++) {
            for (int b = a + 1; b <= n; b++) {
                if (arr[a][b] == 0) continue; // a->b로 가는 비행기가 없으면 다음 비행기 탐색

                // a 도시를 j번 째 지났다면 j번째의 기내식 최대값 + a->b로 가는 비행기의 기내식 값
                for (int j = 1; j < m; j++) {
                    if (dp[a][j] != -1) {
                        dp[b][j + 1] = Math.max(dp[b][j + 1], dp[a][j] + arr[a][b]);
                    }
                }
            }
        }


        System.out.println(Arrays.stream(dp[n]).max().orElse(0));

    }

}

❗ 오답노트 / 필요한 지식

1.  처음에 방문하지 않았다면 dp[a][j] = 0으로 했는데 정말 잘못된 풀이였다. 예를 들어 2 -> 3  10000 으로 3이 끝이라 했을때 이때 기내식 점수는 최댓값이라 해도 1에서 2로 가는 경로가 없다면 이 경로로는 불가능하다.
2. 역시 테스트 케이스를 잘 만들 줄 알아야한다. 항상 고민하고 생각하자.