[PS] BOJ17484 진우의 달 여행 ( DP ) with JAVA

17484번: 진우의 달 여행 (Small)

 

 

◎ 문제풀이

 

진우가 지구에서 달까지 높이마다 정해진 방향으로 이동할 때, 비용의 최솟값을 구하는 문제이다.

 

처음에는 높이마다 정해진 방향으로 이동하므로, 계층에 따른 모든 경우의 수를 완전탐색하는 DFS 알고리즘을 떠올렸다. 그러다가 문제가 탐색(재귀호출)으로 어떤 조합을 찾기보다는 최적해를 구하는 문제이므로, 메모리제이션을 활용한 DP 풀이가 더 적합하다는 생각으로 바뀌었다. 

 

이동에는 3가지 경우가 있다.

 

1) 좌측 아래로 대각선 이동

2) 아래로 이동

3) 우측 아래로 대각선 이동

 

예를 들어보자. 

 

 

 

 

 

 

7번 노드로 이동하는 경우는 3가지가 있다. 

 

1) 좌측 아래로 대각선 이동 ( 4번 )

2) 아래로 이동 ( 5번 )

3) 우측 아래로 대각선 이동 ( 6번 )

 

4번으로 들어오는 경우, 같은 방향으로 연속이동이 안되므로 4번은 2번과 3번으로 들어오는 경우만 가능하다. 이를 dp코드로 정리하면 아래와 같다. 

 

dp[i][j][0] = Math.min(dp[i-1][j-1][1],dp[i-1][j-1][2]) + matrix[i][j]; // 좌측 아래로 대각선 이동
dp[i][j][1] = Math.min(dp[i-1][j][0],dp[i-1][j][2]) + matrix[i][j]; // 아래로 이동
dp[i][j][2] = Math.min(dp[i-1][j+1][0],dp[i-1][j+1][1]) + matrix[i][j]; // 우측 아래로 대각선 이동

 

 

Bottom-up 방식으로 0부터 n-1까지 구해주고 n-1일때 비용의 최솟값을 구해주면 된다. 

 

◎ 코드

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

//BOJ17484 진우의 달 여행
public class Main {

    static int n,m;
    static int[][] matrix;
    static int[][][] dp;

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

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

        matrix = new int[n][m];
        dp = new int[n][m][3];

        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++){
                matrix[i][j] = Integer.parseInt(st.nextToken());
                if(i==0) Arrays.fill(dp[i][j],matrix[i][j]);
                else Arrays.fill(dp[i][j],Integer.MAX_VALUE);
            }
        }

        for(int i=1;i<n;i++){
            for(int j=0;j<m;j++){
                if(j!=0) dp[i][j][0] = Math.min(dp[i-1][j-1][1],dp[i-1][j-1][2]) + matrix[i][j];
                dp[i][j][1] = Math.min(dp[i-1][j][0],dp[i-1][j][2]) + matrix[i][j];
                if(j!=m-1) dp[i][j][2] = Math.min(dp[i-1][j+1][0],dp[i-1][j+1][1]) + matrix[i][j];
            }
        }

        int ans = Integer.MAX_VALUE;
        for(int j=0;j<m;j++){
            int minValue = dp[n-1][j][0];
            for(int k=1;k<3;k++){
                minValue = Math.min(minValue,dp[n-1][j][k]);
            }
            ans = Math.min(ans,minValue);
        }

        System.out.println(ans);


    }
}