[BaekJoon] 2169 로봇 조종하기

1.  문제 링크

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

2.  문제

요약

• NASA에서 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈는데, 화성의 지형을 N x M 배열로 단순화하여 생각하기로 하였습니다.
• 로봇은 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만 위쪽으로는 이동할 수 없습니다.
• 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 하였습니다.
• 각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 합니다.
• 위 조건을 만족하면서 탐사한 지역들의 가치의 합이 최대가 되도록 하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 N, M이 주어지고 두 번째 줄부터 N개의 줄에 절댓값이 100보다 작거나 같은 정수인 배열의 각 수가 주어집니다. 이 값은 그 지역의 가치를 나타냅니다.
• 출력: 첫 번째 줄에 최대 가치의 합을 출력합니다.

3.  소스코드

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

public class Main {
    static int N, M;
    static int[][] map;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        M = scanner.nextInt();
        map = new int[N + 1][M + 1];

        for(int row = 1; row <= N; row++) {
            for(int col = 1; col <= M; col++)
                map[row][col] = scanner.nextInt();
        }
    }

    static void solution() {
        int[][] dp = new int[N + 1][M + 1];

        dp[1][1] = map[1][1];
        for(int col = 2; col <= M; col++)
            dp[1][col] = dp[1][col - 1] + map[1][col];

        int[][] temp = new int[2][M + 2];
        for(int row = 2; row <= N; row++) {
            // 왼쪽에서 오는 방향, 위쪽에서 오는 방향 비교
            temp[0][0] = dp[row - 1][1];
            for(int col = 1; col <= M; col++) {
                temp[0][col] = Math.max(temp[0][col - 1], dp[row - 1][col]) + map[row][col];
            }

            // 오른쪽에서 오는 방향, 위쪽에서 오는 방향 비교
            temp[1][M + 1] = dp[row - 1][M];
            for(int col = M; col >= 1; col--) {
                temp[1][col] = Math.max(temp[1][col + 1], dp[row - 1][col]) + map[row][col];
            }

            // 비교한 두 경우를 가지고 더 큰 값을 찾음
            for(int col = 1; col <= M; col++) {
                dp[row][col] = Math.max(temp[0][col], temp[1][col]);
            }
        }

        System.out.println(dp[N][M]);
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4  접근

• 주어진 각 지역의 가치를 map이라는 2차원 배열에 할당합니다.
• dp라는 2차원 배열을 생성하는데, 이 배열은 각 위치에서의 최대 가치를 나타냅니다.
  • 첫 번째 행은 위로 움직이는 경우의 수가 없으니 (1, 1)에서 오른쪽으로 움직여서 가는 경우의 수 밖에 존재하지 않습니다.
  • 그렇기 때문에 dp의 첫 번째 행은 각 위치까지의 map의 값의 합으로 초기화합니다.
• 각 위치로 이동할 수 있는 경우의 수는 왼쪽에서 오는 경우, 위에서 오는 경우, 오른쪽에서 오는 경우가 존재하는데 이를 위해 temp라는 2차원 배열을 생성합니다.
  • temp 배열을 2 x (M + 2) 크기를 가지는데, 행의 index가 0인 경우는 왼쪽에서 오는 경우와 위에서 오는 경우에서의 가치의 최댓값을 나타내고 행의 index가 1인 경우는 오른쪽에서 오는 경우와 위에서 오는 경우에서의 가치의 최댓값을 나타냅니다.
  • 행의 index가 0인 경우에, 즉 왼쪽에서 오는 경우와 위에서 오는 경우에서의 가치의 최댓값을 구할 때는 아래와 같은 식이 성립할 수 있습니다.
    • temp[0][col] = Math.max(temp[0][col - 1], dp[row - 1][col]) + map[row][col];
      • 여기서 row는 현재 행의 index 값, col은 현재 열의 index 값을 나타냅니다.
      • temp[0][col - 1]은 왼쪽에서 오는 경우를 나타내고, dp[row - 1][col]은 위에서 오는 경우를 나타냅니다.
      • 즉, 왼쪽에서 오는 경우와 위에서 오는 경우 중 더 큰 값을 취하고 그 값에 현재 위치의 가치를 더해서 현재 위치에서의 가치의 최댓값을 구합니다.
  • 마찬가지로 index가 1인 경우에, 즉 오른쪽에서 오는 경우와 위에서 오는 경우에서의 가치의 최댓값을 구할 때는 아래와 같은 식이 성립할 수 있습니다.
    • temp[1][col] = Math.max(temp[1][col + 1], dp[row - 1][col]) + map[row][col];
      • 여기서 row는 현재 행의 index 값, col은 현재 열의 index 값을 나타냅니다.
      • temp[1][col + 1]은 오른쪽에서 오는 경우를 나타내고, dp[row - 1][col]은 위에서 오는 경우를 나타냅니다.
      • 즉, 오른쪽에서 오는 경우와 위에서 오는 경우 중 더 큰 값을 취하고 그 값에 현재 위치의 가치를 더해서 현재 위치에서의 가치의 최댓값을 구합니다.
  • 현재 위치에서의 temp의 값을 모두 구했다면 그 중 큰 값을 dp의 현재 위치에서의 값으로 설정합니다.
• 위와 같은 방법으로 (N, M)까지 dp의 값을 구하고 최종적으로 dp[N][M]의 값이 답이 됩니다.