[백준 2169번] 로봇 조종하기 (java)

백준 2169번 : 로봇 조종하기

2169번: 로봇 조종하기

 

다이나믹 프로그래밍을 이용하여 풀이하였다.

오른쪽, 아래쪽으로만 움직일 수 있었다면 문제가 쉬었을텐데, 왼쪽이동이 가능함에 따라 난이도가 올라갔다.

 

처음에 이중for문을 사용하여 현재 위치에서의 최대가치는 dp[i][j] 는

dp[i][j] = Math.max(dp[i][j-1], Math.max(dp[i-1][j], dp[i][j+1]) + w[i][j]

왼쪽에서의 최대가치(dp[i][j-1]), 위쪽에서의 최대가치(dp[i-1][j]), 오른쪽에서의 최대가치(dp[i][j+1]) 중 제일 큰 값 + 현재 위치에서의 가치(w[i][j]) 로 점화식을 세웠더니 오른쪽 방향에서 올 때가 해결되지 않았다.

이중 반복문의 반복순서에 따르면, dp[i][j+1]를 구하는 차례가 dp[i][j]를 구하는 차례보다 나중에 오기 때문에

dp[i][j]를 구할 때의 dp[i][j+1]는 아직 안구해졌기 때문이다. 

따라서 Math.max(dp[i][j-1], Math.max(dp[i-1][j], dp[i][j+1]) 에서 엉뚱한 값이 나오게 된다.

 

 

 

그래서 우선 갔던 길을 다시 가지 않기 위해 dp 배열을 2차원이 아닌 3차원 배열로 생성하였다.

특정 위치 dp[i][j] 에 대하여 왼쪽 방향에서 올 때와, 오른쪽 방향에서 올 때와, 위쪽 방향에서 올 때를 구분하기 위해

dp[i][j][0] : 왼쪽 방향에서 (i, j) 위치로 올 때의 최대 가치

dp[i][j][1] : 위쪽 방향에서 (i, j) 위치로 올 때의 최대 가치

dp[i][j][2] : 오른쪽 방향에서 (i, j) 위치로 올 때의 최대 가치

로 나눠주었다.

 

dp[i][j][0]의 점화식을 세우면,

dp[i][j][0] = Math.max(dp[i][j-1][0], dp[i][j-1][1]) + w[i][j] 이다.

dp[i][j-1][2]의 의미는 (i, j-1)의 오른쪽 방향에서 (i, j-1)로 왔을 때이므로 그렇다면 (i, j-1)의 오른쪽인 (i, j)를 이미 지나왔다는 뜻이다. 그러므로 (i, j)를 두 번 방문하는 것이 된다. (i, j) -> (i, j-1) -> (i, j)

이 경우는 피해야 하므로 dp[i][j][0]를 구 할 때는 dp[i][j-1][2]를 고려하면 안된다.

 

dp[i][j][1]의 점화식을 세우면,

dp[i][j][1] = Math.max(dp[i-1][j][0], Math.max(dp[i-1][j][1], dp[i-1][j][2]) + w[i][j] 이다.

위쪽에서 (i, j)로 올 때는 (i-1, j)를 왼쪽에서 방문한 상태든, 위쪽에서 방문한 상태든, 오른쪽에서 방문한 상태든 상관없다. 어떤 케이스라도 (i, j)를 지나지 않기 때문이다.

 

dp[i][j][2]의 점화식을 세우면,

dp[i][j][2] = Math.max(dp[i][j+1][1], dp[i][j+1][2]) + w[i][j] 이다.

dp[i][j+1][0]의 의미는 (i, j+1)의 왼쪽 방향에서 (i, j+1)로 왔을 때이므로 그렇다면 (i, j+1)의 왼쪽인 (i, j)를 이미 지나왔다는 뜻이다. 그러므로 (i, j)를 두 번 방문하는 것이 된다. (i, j) -> (i, j+1) -> (i, j)

이 경우는 피해야 하므로 dp[i][j][2]를 구 할 때는 dp[i][j+1][0]를 고려하면 안된다.

 

그리고 이중 for문에서 안쪽 for문을 두번 반복하여서 처음에는 왼쪽 -> 오른쪽으로 이동하며 dp[i][j][0], dp[i][j][1]를

넣어주었고 반복문이 끝나면 다시 오른쪽 -> 왼쪽으로 이동하며 dp[i][j][2]를 넣어주었다.

 

 

이렇게 각각 점화식을 세우고 문제를 풀었는데 '틀렸습니다' 가 떴다.

import java.io.*;

public class Main {

	static int N, M;
	static int[][][] dp;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String[] sarr = br.readLine().split(" ");
		N = Integer.parseInt(sarr[0]);
		M = Integer.parseInt(sarr[1]);

		dp = new int[N + 1][M + 1][3];

		for (int i = 1; i <= N; i++) {
			sarr = br.readLine().split(" ");
			for (int j = 1; j <= M; j++) {
				int w = Integer.parseInt(sarr[j - 1]);
				dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = w;
			}
		}

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

			for (int j = 1; j <= M; j++) {
				dp[i][j][0] += Math.max(dp[i][j - 1][0], dp[i][j - 1][1]);
				dp[i][j][1] += Math.max(dp[i - 1][j][0], Math.max(dp[i - 1][j][1], dp[i - 1][j][2]));
			}
			for (int j = M - 1; j >= 1; j--) {
				dp[i][j][2] += Math.max(dp[i][j + 1][1], dp[i][j + 1][2]);
			}
		}

		bw.write(Math.max(dp[N][M][0], dp[N][M][1]) + "\n");
		bw.flush();

	}

}

 

반례는 다음과 같다.

5 5

-1 -1 -1 -1 -1

-1 -1 -1 -1 -1

-1 -1 -1 -1 -1

-1 -1 -1 -1 -1

-1 -1 -1 -1 -1

답이 -9 이어야 하는데 -2가 나왔다. 

문제에서 지형은 (1, 1) 부터 시작한다. 사실상 배열의 인덱스를 행과 열 모두 1부터 표현한 것이 위의 모습이다.

행과 열 모두 인덱스 0부터 표현한다면 아래와 같다.

0  0  0  0  0  0

0 -1 -1 -1 -1 -1

0 -1 -1 -1 -1 -1

0 -1 -1 -1 -1 -1

0 -1 -1 -1 -1 -1

0 -1 -1 -1 -1 -1

 

여기서 각 지형의 가치가 0보다 작은 음수라는 점에서 문제가 생긴다.

dp[i][j][0] = Math.max(dp[i][j-1][0], dp[i][j-1][1]) + w[i][j]

dp[i][j][1] = Math.max(dp[i-1][j][0], Math.max(dp[i-1][j][1], dp[i-1][j][2]) + w[i][j]

dp[i][j][2] = Math.max(dp[i][j+1][1], dp[i][j+1][2]) + w[i][j] 

 

이 점화식에서 지형의 가장자리 부분의 경우,

최대를 찾는 과정에서 0이 -1보다 크기 때문에 0이 선택되는 일이 발생하는 것이다.

따라서 지형 바깥의 인덱스가 0을 포함하는 경우에는 가장자리에 위치한 지형의 가치보다 더 작은 값으로 초기화를 해줘야 한다.

문제에서 지형의 가치는 절대값 100을 넘지 않는다 했다.

지형의 NxM의 가치가 모두 -100일 경우, 지형을 모두 이동한다고 가정하면 -100 * N * M가 되므로

넉넉잡아서 초기값을 -101 * N * M 으로 해주었다.

 

따라서 수정한 소스코드는 아래와 같다.

 

소스코드 :