[백준] 11048 이동하기 - 동적계획법(DP, Dynamic Programming) JAVA

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

11048번: 이동하기

코드설명

DP 문제입니다.

 

문제의 핵심은, 도착하는 지점 기준으로 9시방향, 10시 30분방향, 12시방향 3가지 방향을  기준으로 가장 큰 값을 가져옵니다.

해당사항만 구현하면 메모리제이션을 통해 손쉽게 미로의 이동경로를 파악합니다.

 

또한, 추가로 미로를 움직이는 입장에서 보면 3가지방향, 우측, 우하대각선, 하대각선 이 방향으로만 준규가 이동할 수 있기에 처리하더라도 항상 오른쪽 아래로 이동하기에 for문에서 순서대로 처리하더라도 문제가 없습니다. 만약 8가지 방향으로 이동할경우에는 아예 다른 방문처리 문제가 되며 BFS문제 혹은 DFS문제가 됩니다.

코드

반복문으로 한번에 처리합니다.

import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int T, N, M;
	public static int[] arr = new int[2001];
	public static int[][] dp = new int[1001][1001];
	public static int[] dx= {1,0,1};
	public static int[] dy = {0,1, 1};
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine());	
    		for(int j=1;j<=M;j++) {
    			dp[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	for(int i=1;i<=N;i++) {
    		for(int j=1;j<=M;j++) {
    			int nr = i;
    			int nc = j;
    			int maxValue=dp[i - dx[0]][j - dy[0]];
    			
    			for(int dir=0;dir<3;dir++) {
					nr = i - dx[dir];
					nc = j - dy[dir];
    				
    				if( nr >= 1 && nr <= N && nc >= 1 && nc <= M) {
    					maxValue = Math.max(maxValue, dp[nr][nc]);
    				}
    			}
    			dp[i][j] += maxValue;
    			
    		}
    	}
    	System.out.println(dp[N][M]);
    }
}

하나하나씩 방향을 체크한코드입니다.

import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int T, N, M;
	public static int[] arr = new int[2001];
	public static int[][] dp = new int[1001][1001];
	public static int[] dx= {1,0,1};
	public static int[] dy = {0,1, 1};
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine());	
    		for(int j=1;j<=M;j++) {
    			dp[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	for(int i=1;i<=N;i++) {
    		for(int j=1;j<=M;j++) {
    			int nr = i;
    			int nc = j;
    			int maxValue=dp[i - dx[0]][j - dy[0]];
    			
    			nr = i - dx[0];
				nc = j - dy[0];
    			maxValue = dp[nr][nc];
    			
				nr = i - dx[1];
				nc = j - dy[1];
				maxValue = Math.max(maxValue, dp[nr][nc]);
				
				nr = i - dx[2];
				nc = j - dy[2];
				maxValue = Math.max(maxValue, dp[nr][nc]);
				
				dp[i][j] += maxValue;

    		}
    	}
    	
    	System.out.println(dp[N][M]);
    }
}

 

재귀와 메모이제이션을 활용한 코드입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int answer = 0;
	static int[][] map;
	static int[][] cache;
	static int[] dx = {1, 0, 1};
	static int[] dy = {0, 1, 1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		cache = new int[N][M];
		for(int i=0;i<N; i++) {
			Arrays.fill(cache[i], -1);
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		System.out.println(DFS(0, 0));
		
	}
	
	static int DFS(int r, int c) {
		if(r == N - 1 && c == M - 1) {
			return map[r][c];
		}
		if(cache[r][c] != -1) return cache[r][c];

		int ret = 0;
		for(int dir =0 ; dir < 3; dir++) {
			int nr = r + dx[dir];
			int nc = c + dy[dir];
			if(nr < 0 || nr >= N || nc < 0 || nc >= M) {
				continue;
			}
			ret = Math.max(ret,  DFS(nr, nc) + map[r][c]);
		}
		return cache[r][c] = ret;
	}
	
	
}