[백준] 17484 진우의 달 여행 (Small) - 동적계획법(Dynamic Programming) + 비트마스킹(BitMask) JAVA

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

코드설명

동적계획법(Dynamic Programming) + 비트마스킹(BitMask) 를 활용합니다.

 

문제에서 Cache를 활용해 메모이제이션을 적용합니다.

이번 문제에서는 N과 M의 범위가 작아서 시간초과 걱정을 할 필요는 없었지만, N과 M이 커진다면 메모이제이션으로 중복연산을 피하는 것이 효율적입니다.

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
    private static int N, M, Q;
    private static int[][] arr;
    private static int[][][] cache;
    private static int answer = Integer.MAX_VALUE;
    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());
		
		arr = new int[N][M];
		cache = new int[N][M][15];
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++)
				Arrays.fill(cache[i][j], -1);
		}
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for(int i=0;i<M;i++) {
//			answer= Math.min(answer, func(0, i, 14 ));
			answer= Math.min(answer, func(0, i, (1 << 1) | (1 << 2) | (1 << 3) ));
		}
		System.out.println(answer);
		
		
    }
    
    static int func(int r, int c, int movedBefore) {
    	if(r == N - 1) {
    		return arr[r][c];
    	}
    	
    	if(cache[r][c][movedBefore] != -1) return cache[r][c][movedBefore];
    	
    	//세가지 방향
    	int ret = Integer.MAX_VALUE;
    	if( ((movedBefore) & (1<<1)) > 0) {
    		ret = Math.min(ret, func(r + 1, c + 0, (1<<2) ) + arr[r][c] );
    		
    		if(c + 1 < M)
    			ret = Math.min(ret, func(r + 1, c + 1, (1<<3) ) + arr[r][c] );
    	}
    	if( ((movedBefore) & (1<<2)) > 0) {
    		if(c - 1 >= 0)
    			ret = Math.min(ret, func(r + 1, c - 1, (1<<1) ) + arr[r][c] );
    		if(c + 1 < M)
    			ret = Math.min(ret, func(r + 1, c + 1, (1<<3) ) + arr[r][c] );
    	}
    	if( ((movedBefore) & (1<<3)) > 0) {
			if(c - 1 >= 0)
				ret = Math.min(ret, func(r + 1, c - 1, (1<<1) ) + arr[r][c] );
			
    		ret = Math.min(ret, func(r + 1, c + 0, (1<<2) ) + arr[r][c] );
		}
    	
		return cache[r][c][movedBefore] = ret;
    }
    
    
}