[boj] 로봇 조종하기_2169 java

 

문제를 보자마자 dp인 건 알았지만

dp 초보인 나는 제대로 된 점화식을 작성할 수 없었습니다.

 

import java.io.*;
import java.util.*;

class Main {

	static int[] dx = {0, -1, 0}, dy = {1, 0, -1}; // bfs를 위한 델타 배열 생성(위로는 못 올라감)
	static int[][] mm, arr;
	static int N, M;

	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new int[N][M]; // 유적 금화를 저장하는 배열
		mm = new int[N][M]; // 메모이제이션(위치, 방향 저장)

		// 유적 내 금화 저장
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(bf.readLine());
			for(int j=0;j<M;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		boolean[][] visited = new boolean[N][M];
		
		visited[N-1][M-1] = true;
		mm[0][0] = arr[0][0];
		System.out.println((1000000000+dp(N-1, M-1, visited)));


	}

	public static int dp(int x, int y, boolean[][] visited) {
		// if(mm[x][y] != 0) return mm[x][y];

		int returnVal = arr[x][y];
		int maxRoute = 0;

		// 현 위치 기준 좌, 우, 상 에서 내려오는 경우 중 가장 큰 값 체크
		for(int i=0;i<3;i++) {
			int nX = x+dx[i];
			int nY = y+dy[i];
			if(isInRange(nX, nY) && !visited[nX][nY]) {
				visited[nX][nY] = true;
				maxRoute = Math.max(maxRoute, dp(nX, nY, visited));
				visited[nX][nY] = false;
			}
		}

		// if(x == N-1 && y == M-1) {
		// 	for(int i=0;i<N;i++) {
		// 		for(int j=0;j<M;j++) {
		// 			System.out.print(visited[i][j]+" ");
		// 		}
		// 		System.out.println();
		// 	}
		// }
		
		return mm[x][y] = returnVal + maxRoute;
	}

	public static boolean isInRange(int x, int y) {
		return 0 <= x && x < N && 0 <= y && y < M;
	}

}

 

일단 저는 메모이제이션을 통해 탑다운 방식으로 풀어보려 했어요.

(N-1, M-1) 에서의 최댓값을 구하려면, (N-2, M-1) 과 (N-1, M-2)에서의 최댓값 중 더 큰 것을 고르면 된다고 생각했습니다.

 

하지만 여기서 논리적인 오류가 발생하는데..

 

• (0, 0)에서 시작한다.
• (N-1, M-1)에서의 최댓값을 가지는 경로가 (a, b)를 지난다고 가정했을 때, (a, b)에서의 최댓값을 가지진 않을 수 있다.

이 두 가지를 고려하지 않았습니다...

 

예를 들어봅시다.

3 5

1 1 1 3 4

0 0 5 2 -1

0 0 1 1 1

의 input이 있다고 가정합니다.

 

제 코드로 돌려본다면, 12라는 output이 나오게 됩니다.

하지만 정답은 19 입니다.

 

네

그냥 설계부터 잘못된 코드입니다!

 

아무튼 그래서 다른 방법을 찾게되었고,

• 가장 첫 행에서는 왼쪽에서 오른쪽으로밖에 이동할 수 없다.

라는 점을 깨달았습니다.

 

        // 가장 첫 행 계산하기 -> 우측으로밖에 가지 못함
        mm[0][0] = arr[0][0];
        for(int i=1;i<M;i++) {
            mm[0][i] = mm[0][i-1] + arr[0][i];
        }

 

그래서 mm 배열 중 가장 첫 행은, 직전 값에 해당 칸의 value를 더한 값으로 업데이트 해줬습니다.

 

다음 행부터는 가짓수가 증가합니다.

• 왼쪽에서 오른쪽으로 이동하거나
• 오른쪽에서 왼쪽으로 이동하거나
• 위에서 아래로 이동한다.

이 세 가지입니다.

 

위에서 아래로 순차적으로 내려올 수 있기 때문에, 

두 번째 행부터 차근차근 계산을 해줄겁니다.

 

각 행마다 fromLeft (왼쪽에서 오른쪽), fromRight (오른쪽에서 왼쪽) 배열을 만들어줍니다.

 

fromLeft의 가장 왼쪽 값과, fromRight에서 가장 오른쪽 값은, 위에서밖에 내려와 업데이트 되지 못합니다.

            // 왼쪽의 시작과 오른쪽의 끝은, 위에서밖에 내려오지 못함.
            fromLeft[0] = mm[i-1][0] + arr[i][0];
            fromRight[M-1] = mm[i-1][M-1] + arr[i][M-1];

 

 

 

fromLeft 에서 (a, b) 좌표의 최댓값은, 이전에 저장해놓은 (a-1, b) 값과 (a, b-1) 중 큰 값에서 오게 하면 됩니다.

이것을 왼쪽에서 오른쪽으로 가면서 계속 갱신합니다.

for(int j=1;j<M;j++) fromLeft[j] = Math.max(fromLeft[j-1], mm[i-1][j]) + arr[i][j];

 

 

fromRight 에서 (a, b) 좌표의 최댓값은, 이전에 저장해놓은 (a-1, b) 값과 (a, b+1) 중 큰 값에서 오게하면 됩니다.

이것을 오른쪽에서 왼쪽으로 가면서 계속 갱신합니다.

for(int j=1;j<M;j++) fromRight[M-1-j] = Math.max(fromRight[M-j], mm[i-1][M-1-j]) + arr[i][M-1-j];

 

 

모두 완료가 됐다면,

같은 위치의 fromLeft와 fromRight를 비교하며, 더 큰 값으로 mm 배열에 저장합니다.

            // mm에 값 넣어주기
            for(int j=0;j<M;j++) {
                mm[i][j] = Math.max(fromLeft[j], fromRight[j]);
            }

 

 

전체 코드 보기

package baekjoon;

import java.io.*;
import java.util.*;

public class 로봇조종하기_2169 {

	static int[] dx = {0, -1, 0}, dy = {1, 0, -1}; // bfs를 위한 델타 배열 생성(위로는 못 올라감)
	static int[][] mm, arr;
	static int N, M;

	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new int[N][M]; // 유적 금화를 저장하는 배열
		mm = new int[N][M]; // 메모이제이션(위치, 방향 저장)

		// 유적 내 금화 저장
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(bf.readLine());
			for(int j=0;j<M;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

        // 가장 첫 행 계산하기 -> 우측으로밖에 가지 못함
        mm[0][0] = arr[0][0];
        for(int i=1;i<M;i++) {
            mm[0][i] = mm[0][i-1] + arr[0][i];
        }

        // 다음 행부터 위쪽에서 내려오거나, 왼쪽에서 오거나, 오른쪽에서 오거나..
        for(int i=1;i<N;i++) {
            int[] fromLeft = new int[M];
            int[] fromRight = new int[M];

            // 왼쪽의 시작과 오른쪽의 끝은, 위에서밖에 내려오지 못함.
            fromLeft[0] = mm[i-1][0] + arr[i][0];
            fromRight[M-1] = mm[i-1][M-1] + arr[i][M-1];

            for(int j=1;j<M;j++) {
                fromLeft[j] = Math.max(fromLeft[j-1], mm[i-1][j]) + arr[i][j];
                fromRight[M-1-j] = Math.max(fromRight[M-j], mm[i-1][M-1-j]) + arr[i][M-1-j];
            }

            // mm에 값 넣어주기
            for(int j=0;j<M;j++) {
                mm[i][j] = Math.max(fromLeft[j], fromRight[j]);
            }
        }

        System.out.println(mm[N-1][M-1]);
	}

}