[Java] 다이나믹 프로그래밍 (진우의 달 여행 (Large))

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

17485번: 진우의 달 여행 (Large)

 

3차원 배열을 통해 dp 테이블을 구성하고 (N+1) X M X 3으로 출발지를 의미하는 행을 한층 더 쌓았다.

좌표 dfs 처럼 dx, dy의 범위를 제한하면서 dp 테이블을 업데이트.

 

아래 알고리즘의 기본 점화식

 

dp[nx][ny][중앙] = min( dp[x][y][왼쪽 위], dp[x][y][오른쪽 위] ) + graph[nx][ny]  

 

 

 

 

 

public class Main {

    public static int N, M, x, y, nx, ny;
    public static int[][] graph;
    public static int[] dx = {1,1,1};
    public static int[] dy = {0,-1,1};
    static Integer INF = Integer.MAX_VALUE;
    public static int result = INF;
    public static int[][][] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        for(int i=0; i<M; i++){
            graph[0][i] = 0;
        }

        for(int i=1; i<N+1; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<N+1; i++){
            for(int j=0; j<M; j++){
                for(int k=0; k<3; k++){
                    dp[i][j][k] = INF;
                }
            }
        }

        for(int i=0; i<M; i++){
            for(int j=0; j<3; j++){
                dp[0][i][j] = 0;
            }
        }
        //dp[nx][ny][왼쪽 위] = min(dp[x][y][중간], dp[x][y][오른쪽 위]) + graph[nx][ny]

        for(int i=0; i<N+1;i++){
            for(int j=0; j<M; j++){
                x = i;
                y = j;
                for(int k=0; k<3; k++){
                    nx = x + dx[k];
                    ny = y + dy[k];

                    if(0<=nx && nx<N+1 && 0<=ny && ny<M){
                        if(k == 0) {
                            dp[nx][ny][k] = Math.min(dp[x][y][1], dp[x][y][2]) + graph[nx][ny];
                        } else if (k==1) {
                            dp[nx][ny][k] = Math.min(dp[x][y][0], dp[x][y][2]) + graph[nx][ny];
                        } else if (k==2) {
                            dp[nx][ny][k] = Math.min(dp[x][y][0], dp[x][y][1]) + graph[nx][ny];
                        }
                    }

                }
            }
        }

        for(int i=0; i<N+1; i++){
            for(int j=0; j<M; j++){
                for(int k=0; k<3; k++){
                    System.out.print( i+","+j+","+k+"="+dp[i][j][k]+" ");
                }
                System.out.println();
            }
            System.out.println();
        }

        for(int i=0; i<M; i++){
            for(int j=0; j<3; j++) {
                if (result > dp[N][i][j]) result = dp[N][i][j];
            }
        }
        System.out.println(result);
    }
}