[BOJ] 2169 로봇 조종하기 - Java

✨ DP 

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

2169번: 로봇 조종하기

---

📍 고려해야할 사항 

• 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만 위쪽으로는 이동 X
• 한 번 탐사한 지역은 재탐사 X
• (1, 1)에서 (N, M)까지 갈 때 탐사한 지역들의 가치의 최댓값 구하기

 

 

🕹️ 풀이 방법

우선 0번째 행에 있는 값들은 왼쪽에서부터 이동하면서 합쳐진 값을 기록한다. 이미 탐색한 길은 다시 방문할 수 없으므로 경로가 왼쪽으로부터 이동한 것만 존재하기 때문이다. 

 

dp를 활용해 풀면 되므로 우측 그림처럼 현재 (i, j) 칸 기준으로 왼쪽(i, j-1), 오른쪽(i, j+1), 위쪽(i-1, j)에 있는 값과 현재 칸에 있는 값을 더하여 더 큰 값으로 갱신시켜주면 된다.

 

하지만 한 가지 더 고려해야할 점이 있다. 

 

현재 칸 기준으로 오른쪽에 있는 칸은 갱신되기 전의 값이다.

만약 오른쪽에 있는 수가 더 큰 값으로 갱신된다면 현재 칸도 다시 갱신시켜주어야 하는데 그렇게 되면 상당히 복잡해질 것이다. 

그러므로 temp[2][j] 배열을 생성하여 temp[0][j]에는 왼쪽, 위쪽으로부터 더한 값을, 

temp[1][j]에는 오른쪽, 위쪽으로부터 더한 값을 넣고 두 개의 배열을 비교하여 최종적으로 큰 값을 dp[i][j]에 넣어주면 된다. 

 

그러면 위와 같은 결과가 나온다.

 

 

 

👩‍💻 전체 코드 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class BOJ_2169_로봇조종하기 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] robot = new int[N][M];
        int[][] dp = new int[N][M];

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                robot[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dp[0][0] = robot[0][0];

		// 0번째 행 값 채우기
        for(int i=1; i<M; i++){
            dp[0][i] = robot[0][i]+dp[0][i-1];
        }

        int[][] temp = new int[2][M];

        for(int i=1; i<N; i++){
        
            // 좌&상
            temp[0][0] = robot[i][0]+dp[i-1][0];
            for(int j=1; j<M; j++){
                temp[0][j] = Math.max(temp[0][j-1], dp[i-1][j])+robot[i][j];
            }

            // 우&상
            temp[1][M-1] = robot[i][M-1]+dp[i-1][M-1];
            for(int j=M-2; j>=0; j--){
                temp[1][j] = Math.max(temp[1][j+1], dp[i-1][j])+robot[i][j];
            }

            for(int j=0; j<M; j++){
                dp[i][j] = Math.max(temp[0][j], temp[1][j]);
            }
        }
        bw.write(dp[N-1][M-1] + " ");
        bw.flush();
        bw.close();
    }
}