[백준] 2169 로봇 조종하기[JAVA]

문제링크 : www.acmicpc.net/problem/2169

2169번: 로봇 조종하기

로봇은 왼쪽, 오른쪽 ,아래쪽으로만 움직일 수 있다. N,M까지 이동하는데 가치의 합이 최대가 되는 경우의 그 가치의 합을 출력하는 문제다. 가치는 음수가 될 수 있는 것에 유의한다. 

모든 경로를 탐색하며 가치의 합이 최대인 경우를 저장하는 방식을 쉽게 생각해볼 수 있다.

 

1,1에서 N,M까지의 가치의 최대합은 1,1에서 특정 지점까지의 가치의 최대합 + 그 특정 지점에서 N,M까지의 가치의 최대의 합이되는 특정 지점을 모두 탐색해보는 소문제로 생각해볼 수 있다. 이렇게 나누면 특정 지점에서 N,M까지의 최대합을 구했을 때 다시 그 위치에 도달했을 때 이미 계산된 값을 활용해서 재귀탐색을 더 진행하지 않아도 된다.

 

다만 여기서 주의해야할 점이 있는데, 이동 가능한 방향이 세 방향이고 왔던 길을 다시 탐색하지 않기 때문에 해당 특정 지점에서 갈 수 있는 루트가 제한적이라는 것이다. 특정 지점을 위쪽 방향에서 내려왔다면 왼쪽,오른쪽, 아래로 이동하여 N,M까지 가는 길 중의 최댓값, 오른쪽에서 왔다면 아래, 왼쪽으로 가는 길 중의 최댓값, 왼쪽에서 왔다면 아래, 오른쪽으로 가는 길 중의 최댓값을 구하게 된다.

 

이러한 세 가지 경우를 고려하지 않고 최대 한가지의 경우만 탐색해서 도출한 값으로 메모이제이션을 하고서 다음 탐색시 특정 지점에 도달했을 때 재귀탐색을 멈추는 코드를 작성하면 잘못된 최댓값을 도출할 확률이 3분의2가 된다. 따라서 메모이제이션 배열인 dp를 세 방향을 고려해주어 모두 탐색해주도록 했다.

 

import java.io.*;
import java.util.*;
public class Main {
	public static int N,M;
	public static int board[][];
	public static int dp[][][];
	public static int dir[][] = {{0,1},{1,0},{0,-1}};
	public static boolean visited[][];
	
	public static boolean isBoundry(int y,int x){
		if(y<1 || x<1 || y > N || x>M) return false;
		return true;
	}
	
	public static int dfs(int y,int x,int direction){
		if(y==N && x ==M) return board[N][M];
		if(dp[y][x][direction]!=-1) return dp[y][x][direction];
		visited[y][x] = true;
		int ans = -200000;
		for(int i=0;i<3;i++){
			int ny = y + dir[i][0];
			int nx = x + dir[i][1];
			if(!isBoundry(ny,nx) || visited[ny][nx]) continue;
			ans = Math.max(ans, dfs(ny,nx,i) + board[y][x]);
		}
		visited[y][x] = false;
		return dp[y][x][direction] = ans;
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		visited = new boolean[N+1][M+1];
		board = new int[N+1][M+1];
		dp = new int[N+1][M+1][3];
		
		for(int i=1;i<=N;i++){
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<=M;j++){
				board[i][j] = Integer.parseInt(st.nextToken());
				for(int k=0;k<3;k++){
					dp[i][j][k] = -1;
				}
			}
		}
		System.out.println(Math.max(dfs(1,1,0),dfs(1,1,1)));
		
	}

}