[백준] 14430 자원 캐기 - 동적계획법(Dynamic Programming, DP) JAVA

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

코드설명

동적계획법(Dynamic Programming, DP)  을 활용합니다.

 

문제를 읽다보면, 해당 함수가 최적 부분 구조(Optimial Substructure) 형태를 이룬다는 것을 알 수 있습니다.

해당 함수를 최적 부분 구조의 관점에서 정의합니다.

DFS(int r, int c ) : [r][c] 에서 시작했을때, [N][M]에 갈때의 최대 자원을 반환한다.

라는 함수를 정의하여 풀어낼 수 있습니다.

 

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K;
	static int answer = 0;
	static int[][] matrix;
	static int[][] cache;
	static int[] dx = {1, 0};
	static int[] dy = {0, 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());
		
		matrix = new int[N][M];
		cache = new int[N][M];
		for(int i=0;i<N;i++) {
			Arrays.fill(cache[i], -1);
		}
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		if(matrix[0][0] == 1) answer += 1;
		answer += DFS(0, 0);
		
		System.out.println(answer);
	}
	
	static int DFS(int r, int c) {
		if(r == N-1 && c == M-1) {
			return 0;
		}
		if(cache[r][c] != -1) return cache[r][c];
		
		int ret = 0;
		for(int dir = 0; dir < 2; dir++) {
			int nr = r + dx[dir];
			int nc = c + dy[dir];
			if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
			
			if(matrix[nr][nc] == 1) {
				ret = Math.max(ret, DFS(nr, nc) + 1);
			}else {
				ret = Math.max(ret, DFS(nr, nc));
			}
		}
		return cache[r][c] = ret;
	}
	
}

 

코드2입니다.

DFS에서 언제 더해질것을 처리하느냐에 따라 달라집니다.

개인적으로는 코드1이 더 간단한것같습니다.

아래 코드에서 유의할점은, ret값과 maxVal 값을 따로 처리해주어야 합니다.

ret값은 먼저 현재 [r][c] 위치에서 자원을 파고,

DFS(nr, nc)는 [nr][nc] 위치에서의 최대 자원을 반환합니다.

그러므로 maxVal로 따로 변수를 만들어서 처리하여야 값이 올바르게 갱신됩니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K;
	static int answer = 0;
	static int[][] matrix;
	static int[][] cache;
	static int[] dx = {1, 0};
	static int[] dy = {0, 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());
		
		matrix = new int[N][M];
		cache = new int[N][M];
		for(int i=0;i<N;i++) {
			Arrays.fill(cache[i], -1);
		}
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		answer = DFS(0, 0);
		System.out.println(answer);
	}
	
	static int DFS(int r, int c) {
		if(r == N-1 && c == M-1) {
			if(matrix[r][c] == 1)
				return 1;
			return 0;
		}
		
		if(cache[r][c] != -1) return cache[r][c];
		
		int ret = 0;
		if(matrix[r][c] == 1) ret += 1;
		int maxVal = 0;
		for(int dir = 0; dir < 2; dir++) {
			int nr = r + dx[dir];
			int nc = c + dy[dir];
			if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
			maxVal = Math.max(maxVal, DFS(nr, nc));
		}
		ret += maxVal;
		return cache[r][c] = ret;
	}
	
}

 

코드2 보다 더 깔끔한 코드입니다.

ret 값에 현재 위치의 자원을 DFS가 처리된 이 후에 더해짐으로써, 영향을 주지 않습니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K;
	static int answer = 0;
	static int[][] matrix;
	static int[][] cache;
	static int[] dx = {1, 0};
	static int[] dy = {0, 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());
		
		matrix = new int[N][M];
		cache = new int[N][M];
		for(int i=0;i<N;i++) {
			Arrays.fill(cache[i], -1);
		}
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		answer = DFS(0, 0);
		System.out.println(answer);
	}
	
	static int DFS(int r, int c) {
		if(r == N-1 && c == M-1) {
			return matrix[r][c];
		}
		
		if(cache[r][c] != -1) return cache[r][c];
		
		int ret = 0;
		for(int dir = 0; dir < 2; 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));
		}
		ret += matrix[r][c];
		return cache[r][c] = ret;
	}
	
}

 

코드 버전 3.

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, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int answer = 0;
	static int[][] matrix = new int[301][301];
	static int[][] cache = new int[301][301];
	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=0; i<301; i++) Arrays.fill(cache[i], -1);
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				matrix[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 matrix[r][c];
		if(cache[r][c] != -1) return cache[r][c];
		
		int ret = 0;
		int temp1 = 0, temp2 = 0;
		if(c + 1 < M) temp1 = DFS(r, c + 1);
		if(r + 1 < N) temp2 = DFS(r + 1, c);
		ret = Math.max(temp1, temp2) + matrix[r][c];
		
		return cache[r][c] = ret;
	}
}