[백준] 2169 - 로봇 조종하기(Java)

문제 파악

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

 

풀이

보자마자 직관적으로 떠올린 풀이는 DFS / DP이다.

하지만 DFS로 접근할 경우, 같은 행에서 좌우 이동이 가능하기 때문에
방문 처리 여부에 따라 무한 루프 또는 최적 경로 차단 문제가 발생한다.

규칙을 찾기 위해 재방문하지 않고, 위쪽으로 방향을 틀지 않는 로봇의 경로를 그려보았다

로봇 경로

N번째 행에서의 로봇의 경로는 

• N + 1 행으로 아랫방향 이동 : ⬇️
• 우측으로만 이동 : ⬇️ ➡️➡️➡️
• 좌측으로만 이동 : ⬅️⬅️⬅️ ⬇️

뿐이다. 만약 우측으로 갔다가 좌측으로 간다면 반드시 같은 칸을 재방문하게 되므로 규칙에 위배된다.
👉 즉, 한 행 안에서는 한 방향만 선택 가능하다는 중요한 제약이 생긴다.

 

DP 상태 정의

그럼 DP 배열을 선언해 보자

DP[i][j] = (i, j) 위치까지의 누적 최댓값

그러나 (i,j) 위치에서 누계 최댓값을 구한다고 해도 우측 (i, j+1)에서 이동한 건지, 좌측(i, j-1)에서 이동한 건지 분리하지 않는다면 누적 값과 상태가 섞이게 된다.

 

따라서 두 가지 상태를 분리해야 한다. 오른쪽만을 택하는 경로, 왼쪽만을 택하는 경로 말이다 😅

 

나는 3차원 배열을 사용하여 3번째 차원의 0, 1에 각각 오른쪽으로 가는 경로의 누계 최댓값(DP [i][j][0]), 왼쪽으로 가는 경로의 누계 최댓값(DP [i][j][1])을 할당했다

 

그러나 편의를 위해 DP 배열을 LEFT, RIGHT 로 나누어 정리하자면 다음과 같다.

RIGHT[i][j] : (i, j)에 오른쪽 방향으로 도달한 최대 누적값
LEFT[i][j] : (i, j)에 왼쪽 방향으로 도달한 최대 누적값

 

 

점화식 세우기

다음으로 점화식을 세워 보도록 하자

 

⬅️ LEFT[i][j]

왼쪽 방향으로 도달했다는 것은

• 위에서 내려왔거나
• 같은 행에서 오른쪽에서 왼쪽으로 이동해 왔다는 의미다.

따라서 다음 세 경우 중 최댓값을 선택하여 (i,j) 위치의 가치를 더해준다.

LEFT[i][j] = max(LEFT[i-1][j], RIGHT[i-1][j], LEFT[i][j+1]) + ARR[i][j]

col -> 1 순서로 훑으며 값을 갱신해 주자

 

➡️ RIGHT[i][j]

오른쪽 방향으로 도달한 경우 역시 마찬가지다

• 위에서 내려왔거나
• 같은 행에서 왼쪽에서 오른쪽으로 이동해 왔다는 의미다.

RIGHT[i][j] = max(LEFT[i-1][j], RIGHT[i-1][j], RIGHT[i][j-1]) + ARR[i][j]

1 -> col 순서로 훑으며 값을 갱신해 주자

 

 

초기화

모든 DP의 값은 최솟값으로 채워 주고, 첫 번째 행을 채워 넣어준다.

첫 번째 행은 (1,1)에서 출발하여 오른쪽으로만 갈 수 있으므로, RIGHT[1][1] ~ RIGHT[1][col] 까지를 누적 하여 채워줄 수 있다.

 

 

팁

0번째, col 및 row 번째 인덱스의 처리를 쉽게 하기 위하여, 배열 크기를 row+2, col+2로 선언하여 사용하면 훨씬 편하다.

 

코드

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

public class Main {
    public static final int IMP = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tok = new StringTokenizer(br.readLine(), " ");
        int r = Integer.parseInt(tok.nextToken());
        int c = Integer.parseInt(tok.nextToken());
        int[][] arr = new int[r + 1][c + 1];
        int[][][] dp = new int[r + 2][c + 2][2];
        for (int i = 1; i <= r; i++) {
            tok = new StringTokenizer(br.readLine());
            for (int j = 1; j <= c; j++) {
                arr[i][j] = Integer.parseInt(tok.nextToken());
            }
        }
        for (int i = 0; i < r + 2; i++) {
            for (int j = 0; j < c + 2; j++) {
                dp[i][j][0] = dp[i][j][1] = IMP;
            }
        }
        // 1행 초기화
        dp[1][1][0] = arr[1][1];
        for (int i = 2; i <= c; i++) {
            dp[1][i][0] = dp[1][i - 1][0] + arr[1][i];
        }
        for (int i = 2; i <= r; i++) {
            // (l -> r) 채우기
            for (int j = 1; j <= c; j++) {
                dp[i][j][0] = Math.max(Math.max(dp[i - 1][j][0], dp[i - 1][j][1]), dp[i][j - 1][0]) + arr[i][j];
            }
            // (r -> l) 채우기
            for (int j = c; j >= 1; j--) {
                dp[i][j][1] = Math.max(Math.max(dp[i - 1][j][0], dp[i - 1][j][1]), dp[i][j + 1][1]) + arr[i][j];
            }
        }
        System.out.println(Math.max(dp[r][c][0], dp[r][c][1]));
    }
}
code