BOJ#2196 로봇 조종하기

BOJ#2196 로봇 조종하기

* 문제

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

Olympiad > 한국정보올림피아드 > KOI 2002 > 고등부 1번

* 풀이

꽤 어려운.. 문제인 것 같습니다.

풀이는 다른 블로그에 자세히 나와 있으니, 저는 제가 어떻게 생각을 했는지 써보겠습니다.

1. 처음 한 생각은 Backtracking 입니다. 의외로 쉽게 풀릴 것 같습니다.

2. 인풋값의 사이즈를 봅니다. 1000 * 1000 사이즈면 Backtracking 형식으로는 풀 수 없을 것 같습니다. (시간 초과)

3. Dynamic Programming으로 방향을 잡습니다.

4. dp를 정의합니다. dp[i][j] : (1, 1)에서 (i, j)에 도달할 때 최대 비용

5. 왼쪽, 오른쪽, 아래쪽으로만 이동할 수 있다. 

   -> 현재 지역을 기준으로 하면 왼쪽, 오른쪽, 위쪽에서만 접근이 가능하다.

   -> 현재 지역은 아래쪽에서는 접근할 수 없다.

   -> 그렇다면 1행의 경우에는 아래쪽과는 상관 없이 1행 자체에서 dp값을 확정할 수 있다.

   -> 2행의 경우는 1행에서, 3행의 경우에는 2행에서, .. , N행의 경우에는 N-1행에 따라서 값이 정해진다.

   -> 1행부터 N행까지 행 단위로 알고리즘을 진행해보자.

6. 1행의 지역은 dp 정의에 따라 왼쪽에서만 접근이 가능하다. 1행의 dp값을 확정해보자.

7. 2행~N행의 경우, 1행처럼 값이 바로 확정될 수 없다. 왜냐하면 여러 방향(위쪽, 왼쪽, 오른쪽)에서 접근이 가능하기 때문이다.

8. 2행~N행의 임의의 셀에서 상황을 다시 따져보자.

9. 위에서 접근하는 경우가 있고, 왼쪽 경로에서 접근하는 경우, 오른쪽 경로에서 접근하는 경우가 있다.

10. 여기서 중요한 점은, 한번 방문한 지역은 다시 방문하지 못하므로

11. 왼쪽 경로에서 접근하는 경우와 오른쪽 경로에서 접근하는 경우가 명확히 구분될 수 있다는 점이다.

(임의의 셀을 기준으로 왼쪽 갔다가 오른쪽 갔다가 할 수 없다는 것이다.)

12. 따라서 1) 위쪽, 왼쪽에서만 접근하는 경우, 2) 위쪽, 오른쪽에서만 접근하는 경우를 명확히 구분하고

13. 두 경우의 값의 최대값을 dp값으로 지정해준다.

!! 다시 한번 주의 : 

2~N번째 행에 대해서

위쪽, 왼쪽에서만 접근하는 경우의 값을 모두 구하고,

위쪽, 오른쪽에서만 접근하는 경우의 값을 별도로 모두 구한 후

그 이후에 값을 비교해준다.

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%232169_ControlRobot/src

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

/**
 * BOJ#2169 로봇 조종하기
 * https://www.acmicpc.net/problem/2169
 */

public class Main {

    static int[][] mapValue = new int[1003][1003];
    static int[][] dp = new int[1003][1003];    // dp[i][j] : (1, 1)에서 (i, j)까지 도달할 때 최대 비용
    static int[][][] tempDP = new int[2][1003][1003];

    public static void main(String[] args) throws IOException {

        int N, M; // 지형의 크기

        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= N; i++) {

            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {

                mapValue[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // Solve
        dp[1][1] = mapValue[1][1];

        // i = 1
        // : 1행의 경우 위쪽에서 접근할 수 없고, 오른쪽에서도 접근할 수 없다.
        for (int j = 2; j <= M; j++) {

            dp[1][j] += dp[1][j - 1] + mapValue[1][j];
        }

        // i = 2 ~ N
        // : 각 행에서 1열부터 M열까지 진행한다.
        for (int i = 2; i <= N; i++) {

            // 위쪽과 왼쪽에서 오는 경우
            tempDP[0][i][1] = dp[i - 1][1] + mapValue[i][1];
            for (int j = 2; j <= M; j++) {

                tempDP[0][i][j] = Math.max(dp[i - 1][j], tempDP[0][i][j - 1]) + mapValue[i][j];
            }

            // 위쪽과 오른쪽에서 오는 경우
            tempDP[1][i][M] = dp[i - 1][M] + mapValue[i][M];
            for (int j = M - 1; j >= 1; j--) {

                tempDP[1][i][j] = Math.max(dp[i - 1][j], tempDP[1][i][j + 1]) + mapValue[i][j];
            }

            // 둘 중 max 값을 취한다
            for (int j = 1; j <= M; j++) {

                dp[i][j] = Math.max(tempDP[0][i][j], tempDP[1][i][j]);
            }
        }

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

    } // main
}