[백준] 로봇 조정하기 2169번 (java) 3차원 dp

출처 : https://www.acmicpc.net/problem/2169

 

풀이 방법

해당 문제에서 다른 dp문제와 다르게 고려해야 할 점은 음수 값을 가지는 칸이 있다는 것과 최단 거리가 아니라 가치의 합이 최대이기 때문에 빙 둘러서 오는 것이 답이 될 수 있다는 점이다.

 

우선 빙 둘러서 오는 것이 답이 될 수 도 있는데 여기서 고려해야 할 점은 한 번 방문한 점은 다시 방문하면 안 된다는 것이다.

그렇기 때문에 backtracking을 사용해야함을 알 수 있다.

 

또한 같은 위치라도 어느 방향에서 오느냐에 따라 해당 위치에서의 최대 값이 달라지므로 3차원 dp를 사용해서 [y][x][dir] 즉 y, x를 dir 방향으로 방문했을 때 최대 값으로 메모리제이션을 했다.

 

여기서 음수 값이 존재하기 때문에 dp의 초기 값을 Integer.MIN_VALUE로 설정하게 된다면 언더플로우가 발생할 수 있기 때문에 조심해야 한다.

 

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


public class P_2169 {
    static int n, m;
    static int[][] arr = new int[1001][1001];
    static int[][] visited = new int[1001][1001];
    static int[][][] dp = new int[1001][1001][3];
    static int[] dy = {1, 0, 0};
    static int[] dx = {0, -1, 1};
    static final int NINF = -987654321;

    //dp로 풀이할 떄 완벼한 분리가 되지 않음 경로가 여러개 가능하기 때문에
    public static int dfs(int y, int x, int dir) { //y, x에 dir방향에서 왔다 라고
        if (y == n-1 && x == m-1) return arr[y][x];
        if (dp[y][x][dir] != NINF) return dp[y][x][dir];
        int ret = NINF;
        visited[y][x] = 1;
        for (int i = 0;i < 3; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
            if (visited[ny][nx] == 1) continue;
            ret = Math.max(ret, dfs(ny, nx, i));
        }
        dp[y][x][dir] = ret + arr[y][x];
        visited[y][x] = 0;
        return dp[y][x][dir];
    }


    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        for (int i = 0; i < 1001; i++) {
            for (int j = 0; j < 1001; j++) {
                for (int k = 0; k < 3; k++) {
                    dp[i][j][k] = NINF;
                }
            }
        }
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(dfs(0, 0, 0));
    }
}