진우의 달 여행 (Large)

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

 

접근법

DFS

기존에 접근했던 방식은 DFS, 백트래킹을 사용하여 문제를 풀이했다. 하지만, 문제에서 주어진 방향은 3개고, N과 M의 최댓값이 1,000이기 때문에 최악의 케이스엔 3^(1000*1000)이 나오기 때문에 당연히 시간초과가 발생한다.

 

엠로 코테에서도 3^(200*200)이 나왔기 때문에 시초가 발생할 것이다.

 

DP

다른 사람들의 풀이를 보면, DP를 사용하여 풀이하였다.

DP[i][j][n]: (i,j)위치에서 n방향으로 도달했을 때의 최소 비용
n = 0 (왼쪽 아래 방향)
n = 1 (바로 위)
n = 2 (오른쪽 아래 방향)

 

출처: https://infinitecode.tistory.com/96

 

이 그림을 보면, 5로 도달하는데 3가지 케이스가 있음을 알 수 있다.

그리고 중요한 조건이 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다.

• 왼쪽에서 왔을 때 (dp[i][j][0]): dp[i-1][j] 에서 중간 또는 오른쪽 값
• 중앙 dp[i][j][1]: dp[i-1][j]에서 왼쪽 또는 오른쪽 값
• 오른쪽 (dp[i][j][2]): dp[i-1][j+1]에서 왼쪽 또는 중간값

 

이런식으로 dp값들을 계산해 나가되, 2개의 엣지 케이스를 고려해야한다.

`왼쪽` 끝에 있을 때 -> 현재 왼쪽 끝에 있다고 가정할 때, 이전 위치를 보면 왼쪽에서 올 수 없는 상황이다. 따라서 중앙, 오른쪽에서 내려올 케이스만 고려해야한다.

마찬가지로, `오른쪽` 끝에 있을 때도 왼쪽에서 왔을 때와 중앙 값만을 고려해서 계산해줘야 한다.

 

최종적으로, 마지막 줄에 있는 dp값들을 돌면서 왼쪽, 중앙, 오른쪽의 최솟값을 계산해주면 된다.

 

코드

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

public class boj17485 {
    static int n, m;
    static int[][] board;
    static int[] dx = {1,1,1};
    static int[] dy = {-1,0,1};
    static boolean[][] visited;
    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());
        board = new int[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int [][][] dp = new int[n][m][3]; // dp[i][j][이전 방향에서 온 값]
        for(int i = 0; i < m; i++) {
            dp[0][i][0] = board[0][i];
            dp[0][i][1] = board[0][i];
            dp[0][i][2] = board[0][i];
        }

        // 0 -> 왼쪽, 1 -> 위, 2-> 오른쪽
        int INF = 10000000;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < m; j++) {

                if (j == 0) {
                    dp[i][j][0] = INF; // 왼쪽 위에서 올 수 없으므로
                    dp[i][j][1] = Math.min(dp[i-1][j][0] + board[i][j], dp[i-1][j][2] + board[i][j]);
                    dp[i][j][2] = Math.min(dp[i-1][j+1][0] + board[i][j], dp[i-1][j+1][1] + board[i][j]);
                }

                else if (j == m-1) {
                    dp[i][j][0] = Math.min(dp[i-1][j-1][1] + board[i][j], dp[i-1][j-1][2] + board[i][j]);
                    dp[i][j][1] = Math.min(dp[i-1][j][0] + board[i][j], dp[i-1][j][2] + board[i][j]);
                    dp[i][j][2] = INF;
                }

                else {
                    dp[i][j][0] = Math.min(dp[i - 1][j - 1][1] + board[i][j], dp[i - 1][j - 1][2] + board[i][j]);
                    dp[i][j][1] = Math.min(dp[i-1][j][0] + board[i][j], dp[i-1][j][2] + board[i][j]);
                    dp[i][j][2] = Math.min(dp[i-1][j+1][0] + board[i][j] , dp[i-1][j+1][1] + board[i][j]);
                }
            }
        }

        int res = Integer.MAX_VALUE;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < 3; j++) {
                res = Math.min(res, dp[n - 1][i][j]);
            }
        }
        System.out.println(res);

    }
}