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; } }
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 15787 기차가 어둠을 헤치고 은하수를 - BitMask(비트마스크) JAVA (0) | 2024.09.07 |
---|---|
[백준] 14496 그대, 그머가 되어 - DFS(깊이우선탐색) + BFS(너비우선탐색) JAVA (0) | 2024.09.06 |
[백준] 13565 침투 - DFS(깊이우선탐색) + BFS(넓이우선탐색) JAVA (0) | 2024.09.05 |
[백준] 11724 연결 요소의 개수 - DFS(깊이우선탐색) JAVA (0) | 2024.09.04 |
[백준] 11568 민균이의 계략 - 동적계획법(Dynamic Programming, DP) + LIS(Longest Increasing Subsequence) JAVA (0) | 2024.09.03 |