[백준] 여행 : 2157 - DP

1. 문제

 

 

 

2. 접근

고려해야 하는 조건은 다음과 같다

• 1번에서 시작해서 N으로 끝내야 한다
• 선택할 수 있는 도시는 최대 M개이다.
• a도시에서 b도시로 갈 때 경로가 여러개 주어질 수 있다. 최대값만 얻어야 한다

 

처음 접근은 다익스트라 알고리즘을 사용하는 것이었다. 최대 비용으로 노드를 선택했을 때를 구현하면 될 것 같았다. 하지만 중간에 구현하다가 기내식의 비용이 같을 때는 어떻게 처리하지? 의문이 들었고 그리디적 알고리즘으로 최적의 상황이 해가되는 다익스트라로는 풀 수 없는 것을 깨달았다.

 

어떻게 풀나 찾아봤더니 DP를 이용하는 문제였다.  DP를 2차원 배열 DP[N][M] 선언하고 도시 N을 M번째로 선택했을 떄의 값을 구해준다.

점화식은 다음과 같다

` DP[b][M] = Math.max(DP[b][M], DP[a][M-1])`

이때 a로부터 b로 가는 경로가 있어야하며, a는 b보다 작아야 한다. 그렇기 때문에 연결된 간선 정보를 저장하는 그래프 데이터도 필요하다.

 

코드로 구현하면 다음과 같다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

    public static List<Integer>[] graph;
    public static int [][] graphMap;
    public static int [][] dp;
    public static int N, K, M;
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 마지막 도착 정점
        M = Integer.parseInt(st.nextToken()); // 최대 M개
        K = Integer.parseInt(st.nextToken()); // 개설된 항로의 개수

        graph = new ArrayList [N+1];
        graphMap = new int[N+1][N+1];
        dp = new int[N+1][M+1];

        for(int i=0; i<graph.length; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=0; i<K; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            if(v1 > v2)
                continue;

            if(graphMap[v1][v2] < cost)
                graphMap[v1][v2] = cost;
        }

        for(int i=1; i<= N; i++){
            for(int j=i+1; j<=N; j++){
                if(graphMap[i][j] == 0)
                    continue;
                graph[i].add(j);
            }
        }
        BFS();

        int max = 0;
        for(int i=1; i<=M; i++){

            max = Math.max(max, dp[N][i]);

        }
        bw.write( max+"\n");
        bw.flush();
    }

    public static void BFS(){
        Queue<Node> que = new LinkedList<>();
        que.add(new Node(1, 1));

        while(!que.isEmpty()){
            Node cur = que.poll();
            if(cur.count >= M)
                continue;

            for(int next : graph[cur.vertex]){
                int cost = graphMap[cur.vertex][next];

                if(dp[cur.vertex][cur.count] + cost > dp[next][cur.count+1]){
                    dp[next][cur.count+1] = Math.max(dp[next][cur.count+1],
                            dp[cur.vertex][cur.count] + cost);
                    que.add(new Node(next, cur.count +1));
                }

            }
        }

    }


}

class Node{
    int vertex;
    int count;

    public Node(int vertex, int count) {
        this.vertex = vertex;
        this.count = count;
    }
}