백준 17485 - 진우의 달 여행

Java

17484 / 17485 번 - 진우의 달 여행

문제

접근 방법

17484 과 17485 번 동일한 문제로, 테스트케이스 개수의 차이가 있다. DP를 사용하여 실행 케이스를 줄여서 해결한다.

DP 접근법

먼저 [y,x] 까지 각 지점에 도달하는데 발생한 비용은 배열로 관리할 수 있다. => dp[y][x]

현재 지점 (y, x)에 도달하기 위한 방법은 총 3가지 방법이 있다.

1. 왼쪽 아래로 이동
2. 아래로 이동
3. 오른쪽 아래로 이동

문제의 조건 전에 움직인 방향으로 움직일 수 없다로 인하여, 현재 위치까지 도달하기 위해 이전 지점으로부터 이동한 방향을 추가로 관리한다. => dp[k][n][m] (k: 방향)

• 0 : 왼쪽 아래로 이동
• 1 : 아래로 이동
• 2 : 오른쪽 아래로 이동

따라서 dp[0][2][3]의 경우,

왼쪽 아래 방향으로 {2, 3} 으로 도달했을 때 최소 비용 을 의미한다.

풀이

(1,0) 부터 (n-1, m-1) 까지 모든 위치를 탐색하여, 현재 위치까지 k 방향으로 도달하는 최소 비용 dp[k][y][x] 를 구한다. 3가지 방향으로 올 수 있으므로, k가 0일때, 1일때, 2일때를 각각 DP로 구한다.

=> k 방향으로 도달하는 최소 비용 dp[k][y][x] = 이전 지점에서 다른 방향으로 오는 최소 비용 + 현재 칸의 비용

말로하면 어려우므로, 예시를 들면,

{3,3} 까지 왼쪽 아래로 도달하는 방향 = Min({2,4}까지 바로 아래로 or 오른쪽 아래로 이동한 방법) + 현재 위치의 비용

-> dp[0][3][3] = MIN(dp[1][2][4], dp[2][2][4]) + map[3][3];

이 된다.

코드

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

public class Main {
    static int[][] space;
    static int[][][] cost;
    static int n,m;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        n = stoi(stk.nextToken());
        m = stoi(stk.nextToken());

        space = new int[n][m];
        cost = new int[3][n][m];

        for(int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            
            for (int j = 0; j < m; j++) {
                space[i][j] = stoi(stk.nextToken());
                for(int k = 0; k < 3; k++) {
                    cost[k][i][j] = 999999999;      // 초기값은 최대 값으로 설정
                }
            }
        }
        // 첫 시작 값 설정
        for(int i = 0; i < m; i++) {
            for(int k = 0; k < 3; k++) {
                cost[k][0][i] = space[0][i];
            }
        }

        sol();
        // 달에 도착한 후, 최소 값을 탐색
        int result = 999999999;
        for(int i = 0; i < m; i++) {
            for(int k = 0; k < 3; k++) {
                if(result > cost[k][n - 1][i]) {
                    result = cost[k][n - 1][i];
                }
            }
        }
        System.out.println(result);
    }

    static void sol(){
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < m; j++) {
                // 왼쪽 아래로 내려갈때
                if(isIn(j + 1)) {
                    cost[0][i][j] = Math.min(cost[1][i - 1][j + 1], cost[2][i - 1][j + 1]) + space[i][j];
                }

                // 바로 밑으로 내려갈때
                cost[1][i][j] = Math.min(cost[0][i - 1][j], cost[2][i - 1][j]) + space[i][j];

                // 오른쪽 아래로 내려갈때
                if(isIn(j - 1)) {
                    cost[2][i][j] = Math.min(cost[0][i - 1][j - 1], cost[1][i - 1][j - 1]) + space[i][j];
                }
            }
        }
    }

    static boolean isIn(int x){
        if(0 <= x && x < m) {
            return true;
        }
        return false;
    }
    public static int stoi(String str){
        return Integer.parseInt(str);
    }
}