백준 2169번: 로봇 조종하기

문제 설명

• https://www.acmicpc.net/problem/2169
• (1,1)에서 (N,M)으로 이동경로에 놓인 숫자의 합이 최대가 되게 이동해야 합니다.
  이동은 왼쪽, 오른쪽, 아래로만 가능하며 하나의 경로에서 같은 칸을 두번 밟으면 안됩니다.

접근법

잘못된 접근
가장 먼저 BFS가 떠올랐습니다. BFS는 일반적으로 모든 이동에 대한 방문처리를 하지 각 경로에 대한 방문처리가 어려워 불가능했습니다.
이후 DFS로 방문처리를 초기화하는 방식으로 구현했지만 시간초과가 발생했습니다.

(i,j)로 진입할 수 있는 경우는 왼쪽, 위, 오른쪽 3가지 입니다. 오른쪽접근이 불가능하면 문제는 쉽습니다.(예제 - Boj 14430 자원 캐기, Boj 10164 격자상의 경로)

우선 위로 이동할 수 없기 때문에 row별로 값을 채워넣어야 했습니다.
처음에는 왼쪽,위쪽 오른쪽 순서로 dp를 업데이트 했는데 이 경우 방문 위치가 중복될 수 있습니다.

위 그림처럼 왼쪽으로 가면서 업데이트 된 값을 그대로 활용한 오른쪽 방문값이 최대값이 될 수 있습니다.
이를 방지하기 위해 왼쪽, 오른쪽 값을 곧바로 dp에 넣는 게 아니라 따로 만든 뒤 비교를 통해 둘 중 하나의 값만 넣어야 합니다.
이에 비해 위에서 접근하는 건 중복이 불가능하기 때문에 두 경우에서 모두 비교해도 괜찮습니다.

정답

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

public class Main {
	static int[] dx = {0,1,0};
	static int[] dy = {1,0,-1};
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[][] board = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int[][] dp = new int[N][M];
		dp[0][0] = board[0][0];
		// 첫줄은 왼쪽에서 도달하는 경우의 수만 존재
		for (int m = 1; m < M; m++) {			
			dp[0][m] = board[0][m]+ dp[0][m-1];
		}
		// 한줄씩 진행
		for (int i = 1; i < N; i++) {
			int[] temp1 = new int[M];
			int[] temp2 = new int[M];			
			
			// 왼쪽 또는 위에서 오는 경우
			temp1[0] = dp[i-1][0] + board[i][0];
			for (int j = 1; j < M; j++) {
				temp1[j] = Math.max(dp[i-1][j], temp1[j-1]) + board[i][j];
			}
			
			// 오른쪽 또는 위에서 오는 경우
			temp2[M-1] = dp[i-1][M-1] + board[i][M-1];
			for (int j = M-2; j >= 0; j--) {
				temp2[j] = Math.max(dp[i-1][j], temp2[j+1]) + board[i][j];
			}
            
            // 왼쪽과 오른쪽 중 어떤게 더 좋은지 비교
			for (int j = 0; j < M; j++) {
				dp[i][j] = Math.max(temp1[j], temp2[j]);
			}
		}
		
		System.out.println(dp[N-1][M-1]);
		
//		for (int i = 0; i < dp.length; i++) {
//			System.out.println(Arrays.toString(dp[i]));
//		}
		
	}

}