BOJ 2169 로봇 조종하기

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

문제

NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.

지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.

각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.

---

출력

첫째 줄에 최대 가치의 합을 출력한다.

---

예제 입력 1

5 5
10 25 7 8 13
68 24 -78 63 32
12 -69 100 -29 -25
-16 -22 -57 -33 99
7 -76 -11 77 15

예제 출력 1

319

---

코드

거의 DFS 방식으로 풀었다.

다만 DFS에 메모이제이션으로 DP를 활용한 방식이다.

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

public class Main {

    static int N, M, UNKNOWN = -100_000_001;
    static int[] dirR = {1, 0, 0}, dirC = {0, 1, -1};
    static int[][] map;
    static boolean[][] visited;
    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());
        map = new int[N][M];
        visited = new boolean[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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                // dp 배열에서 아직 검사하지 않은 블록이라는 의미를 위한 초기화
                Arrays.fill(dp[i][j], UNKNOWN);
            }
        }

        /**
         * 목적지 (N, M)에서의 최대 값은 목적지에서 입력받은 값 그 자체이기 때문에
         * dp 배열에서 목적지 위치의 값을 채워 search 메소드의 재귀를 끝내기 위함
         */
        Arrays.fill(dp[N - 1][M - 1], map[N - 1][M - 1]);

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

    static int search(int r, int c, int dir) {
        if(dp[r][c][dir] != UNKNOWN) return dp[r][c][dir];

        visited[r][c] = true;
        int max = UNKNOWN;
        // 아래, 좌, 우 방향에 있는 블록에서 얻을 수 있는 최대 값을 max에 저장
        for (int i = 0; i < 3; i++) {
            int newR = r + dirR[i], newC = c + dirC[i];
            boolean isInside = newR >= 0 && newR < N && newC >= 0 && newC < M;
            // 아래 혹은 좌, 우 방향에 있는 위치가 map 안에 있고, 아직 방문하지 않았다면 해당 위치 검사 진행
            if(isInside && !visited[newR][newC])
                max = Integer.max(max, search(newR, newC, i));
        }

        visited[r][c] = false;
        return dp[r][c][dir] = map[r][c] + max;
    }
}