[BOJ] 17485번 진우의 달 여행(Large) 자바 풀이 (다이나믹 프로그래밍)

BOJ 17485번 진우의 달 여행(Large) 문제 자바(java) 풀이

• 랭크 : 골드5
• 백준 17485번 진우의 달 여행(Large)

문제정리

1. 지구와 우주 사이는 NxM 행렬로 나타낼 수 있다.
2. 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.
3. 지구->달로 가는 경우 왼쪽 아래, 아래, 오른쪽 아래 3가지의 방향으로만 이동 가능하다.
4. 같은 방향으로 두번 연속 움직일 수 없다.
5. 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙해야한다.

• 달에 도달하기 위해 필요한 연료의 최소값을 계산하자.

문제풀이

데이터의 크기가 크기 때문에 Dynamic Programming(DP) 기법을 적용해서 풀어야 합니다.
dfs로 풀게 되면 시간초과가 나오게 됩니다.

1. 3차원 배열을 만든다(dp[dir][x][y])
   • dir: 이전에 온 방향
   • x,y: 이전에 온 위치
   • 즉 dp[0][1][1]은 (1,1)의 왼쪽 대각선 방향에서 왔을때 최소 연료의 양이다.
2. 다음과 같이 식을 세운다.
   여기서 맨 왼쪽, 오른쪽은 예외처리 해주어야 합니다.( 맨 왼쪽의 경우 왼쪽 대각선 방향에서 올 수가 없음 )
   배열 첫 인덱스의 0은 왼쪽 대각선, 1은 가운데, 2는 오른쪽 대각선에서 온 경우 입니다.
   • dp[0][x][y] = min( dp[1][x-1][y-1], dp[2][x-1][y-1] ) + fuel[x][y]
     이는 (x,y)로 왼쪽 대각선 방향에서 왔을때 최소 연료의 양을 나타낸다. 즉 이전에 왼쪽 대각선 방향에서 왔으면 안된다.
     그러므로 그 이전에 바로 아래로 오는 경우, 오른쪽 대각선 방향에서 왔을 경우의 연료의 양을 비교해서 더 적은 것을 택한다.
     그리고 거기에 현 위치에서 소모되는 연료의 양을 더해준다.
   • dp[1][x][y] = min( dp[0][x-1][y], dp[2][x-1][y] ) + fuel[x][y]
     이는 (x,y)로 바로 위에서 왔을때 최소 연료의 양을 나타낸다. 즉 이전에 바로 위에서 내려왔으면 안된다.
     그러므로 그 이전에 왼쪽 대각선 방향, 오른쪽 대각선 방향에서 왔을때의 연료의 양을 비교해서 더 적은 것을 취한다.
     그리고 거기에 현 위치에서 소모되는 연료의 양을 더해준다.
   • dp[2][x][y] = min( dp[0][x-1][y+1] dp[1][x-1][y+1] ) + fuel[x][y]
     이는 (x,y)로 오른쪽 대각선 방향에서 왔을때 최소 연료의 양을 나타낸다. 즉 이전에 오른쪽 대각선 방향에서 왔으면 안된다.
     그러므로 그 이전에 왼쪽 대각선 방향, 바로 위(가운데)에서 왔을때의 연료의 양을 비교해서 더 적은 것을 취한다.
     그리고 거기에 현 위치에서 소모되는 연료의 양을 더해준다.
3. 식에 따라 모든 위치에서의 값을 계산하고 맨 아래 행에서 가장 작은 값을 구하면 답이다. (dp[dir][n-1][y], dir과 y값을 변화해가며 min 값을 찾는다.)

dp 배열 값 구하기

이 식만을 보고 바로 이해가 된다면 dp문제를 좀 풀어본 사람일 것입니다.
하지만 저 같은 경우 dp문제를 풀어본 경험이 거의 없기 때문에 바로 이해할 수 없었습니다.
가장 좋은 방법은 손으로 직접 모든 값을 구해보며, 아!! 이래서 이렇구나 하고 느껴보는 것입니다.(제가 그럤습니다)
예를 들어 몇 개만 구해보겠습니다. 우선 맨 윗줄은 모든 방향의 값이 그 칸의 연료의 값입니다.(그 전의 위치에서 연료 소모가 없으므로)
그러면 dp[0][0][0] = 'X', dp[1][0][0] = 5, dp[2][0][0] = 5, dp[0][0][1] = 8, dp[1][0][1] = 8, dp[2][0][1] = 8 처럼 초기화가 됩니다.
여기서 (1,0)에서의 연료 소모량을 구해보겠습니다.

- dp[0][1][0]은 맨 왼쪽에서 올 수 없으므로 값이 존재하지 않는다.
- dp[1][1][0] = dp[2][0][0] + fuel[1][0]
    이는 바로 위에서 오는 경우 최소 연료의 양을 구하는 것이다. 이는 그전에 왼쪽 대각선, 오른쪽 대각선 중에 더 작은 연료의 값을 취하면 된다.
    그런데 그 이전에 왼쪽 대각선에서 오는 경우는 없으므로 오른쪽 대각선에서 오는 경우인 dp[2][0][0] 값에다가 현재 필요한 연료의 양(fuel[1][0])을 더하며 된다.
- dp[2][1][0] = min(dp[0][0][1], dp[1][0][1]) + fuel[1][0]
    이는 오른쪽 대각선 에서 오는 경우 최소 연료의 양을 구하는 것이다. 이는 (1,0)의 오른쪽 대각선의 최소 연료의 양을 보면 된다.
    그 중에도 왼쪽 대각선으로 왔을때의 최소 연료의 양(dp[0][0][1]), 가운데에서 왔을때 최소 연료의 양(dp[1][0][1])만 비교하면 된다.
    두 값 모두 8로 같다. 그렇기 때문에 8 + 3 = 11이라는 값을 얻을 수 있다.

나머지도 위와 같은 방식으로 모두 구해주면 마지막 행에서 dp[1][5][0]의 값이 29로 제일 작게 된다. 즉 답은 29이다.
경로는 다음과 같다(↘, ↙, ↘, ↙, ↓). 마지막으로 연료가 4인 부분을 지난다.

dp 배열 표로 나타내기

0	1	2	3
X, 5, 5	8, 8, 8	5, 5, 5	1, 1, X
X, 8, 11	10, 13, 10	16, 13, 9	9, 5, X
X, 20, 19	85, 87, 90	75, 74, 70	14, 14, X
X, 21, 87	20, 86, 75	92, 75, 19	72, 16,X
X, 26, 25	119, 118, 173	76, 20, 17	24, 77, X
X, 29, 122	120,119+95, 20+95	118+67, 17+67, 24+67	17+58, 24+58, X

자바 풀이

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

class Main{    
    static int n,m;
    static int fuel[][];
    // 0: ↘
    // 1: ↙
    // 2: ↓
    static int[][][] dp;

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

        // 전에 움직인 방향으로 움직일 수 없다.

        String[] temp = br.readLine().split(" ");
        n = Integer.parseInt(temp[0]);
        m = Integer.parseInt(temp[1]);
        fuel = new int[n][m];
        dp = new int[3][n][m];

        for(int i=0; i<n; i++) {
            String[] temp2 = br.readLine().split(" ");
            for(int j=0; j<m; j++) {
                fuel[i][j] = Integer.parseInt(temp2[j]);
            }
        }

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

        // 있을 수 없는 값들 큰 값으로 초기화
        for(int i=0; i<n; i++){
            // 맨 왼쪽 끝인데 왼쪽 대각선 방향에서 오는 경우
            dp[0][i][0] = Integer.MAX_VALUE;
            // 맨 오른쪽 끝인데 오른쪽 대각선 방향에서 오는 경우
            dp[2][i][m-1] = Integer.MAX_VALUE;
        }

        for(int i=1; i<n; i++){
            for(int j=0; j<m; j++){
                // 왼쪽 방향, 오른쪽 방향 모두에서 올 수 있는 경우
                if(isValidPosition(j-1) && isValidPosition(j+1)){
                    dp[0][i][j] = Math.min(dp[1][i-1][j-1], dp[2][i-1][j-1]) + fuel[i][j];
                    dp[1][i][j] = Math.min(dp[0][i-1][j], dp[2][i-1][j]) + fuel[i][j];
                    dp[2][i][j] = Math.min(dp[0][i-1][j+1], dp[1][i-1][j+1]) + fuel[i][j];
                }
                else if(!isValidPosition(j-1) && isValidPosition(j+1)){
                    // 오른쪽 끝에 있는 경우
                    dp[1][i][j] = Math.min(dp[0][i-1][j], dp[2][i-1][j]) + fuel[i][j];
                    dp[2][i][j] = Math.min(dp[0][i-1][j+1], dp[1][i-1][j+1]) + fuel[i][j];
                }
                else if(isValidPosition(j-1) && !isValidPosition(j+1) ){
                    // 왼쪽 끝에 있는 경우
                    dp[0][i][j] = Math.min(dp[1][i-1][j-1], dp[2][i-1][j-1]) + fuel[i][j];
                    dp[1][i][j] = Math.min(dp[0][i-1][j], dp[2][i-1][j]) + fuel[i][j];
                }
            }
        }

        int min = Integer.MAX_VALUE;
        // 마지막 행에서 최소값 찾기
        for(int i=0; i<m; i++){
            for(int j=0; j<3; j++){
                min = min > dp[j][n-1][i] ? dp[j][n-1][i] : min;
            }
        }
        System.out.println(min);
        br.close();
    }


    public static boolean isValidPosition(int y) {
        if(y < 0 || y >= m)
            return false;
        return true;
    }
}