[백준] 1890 점프 - 동적계획법(DP, Dynamic Programming) JAVA

passionfruit200 2023. 8. 19. 10:20

2023. 8. 19. 10:20

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

1890번: 점프

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장

www.acmicpc.net

코드설명

dp 문제입니다.

처음에 기본적으로 dp를 해당 위치까지 올 수 있는 경우의 수로 생각하여

각 위치에서 이동거리에 위치한 점에 도달할때마다 아래의 코드와 같이 갱신하도록 설정하는 것까지는 구현을 했습니다.

우선 이 문제를 DP 로 풀 수 있는 이유는, 게임의 진행이 무조건 오른쪽, 아래쪽으로 진행하는 방향이 있기 떄문입니다.

만약에 상하좌우라면, 아래의 코드로는 풀 수 없습니다.

제가 처음에 풀었던 오류 코드입니다.

아래의 코드는 3가지 로직을 빠트렸습니다.

for(int i=0;i<N;i++) {

    for(int j=0;j<N;j++) {

        //오른쪽으로 이동
        int nr = i;
        int nc = j + arr[i][j];

        if(nr >= 0 && nr < N && nc >= 0 && nc < N) {
            dp[nr][nc] += 1;	
        }


        //아래쪽으로 이동
        nr = i + arr[i][j];
        nc = j;
        if(nr >= 0 && nr < N && nc >= 0 && nc < N) {
            dp[nr][nc] += 1;	
        }

    } 
}

만약에 if(arr[i][j] == 0 ) break; 구문이 빠졌습니다.
1. 해당 구문을 통하여 종료시키지 않을경우, 이동이 되지 않아서 같은 위치에 더하게 됩니다.
2. 아래의 코드에서 볼 수 있듯이 dp[nr][nc] 에 중복으로 +1을 하게되어 오류가 납니다.
dp[i][j] > 0 구문이 빠졌습니다.
1. 해당 구문을 통하여 기존에 도착할 수 있는 지점만 작동하도록 처리하여야, 해당 경로를 들어왔다고 판단할 수 있습니다.
2. dp[i][j] > 0 구문을 통하여 이전에 도착한 적이 있다는 처리를 해야합니다.
dp[nr][nc] += 1이 아닌 dp[nr][nc] += dp[i][j] 가 되어야합니다.
1. 해당 코드를 통하여 이전 위치에 올 수 있는 모든 경우의 수를 더해야합니다. 이유는, dp[i][j] ( 해당 위치로 올 수 있는 경우의 수) 가 5가지가 있다고한다면, dp[i][j] 에서 dp[nr][nc]로 이동하였을때 dp[nr][nc] 로 올 수 있는 경우의 수도 5가지가 더해질 것 입니다.
2. 위 로직을 통하여 다른 점에서 dp[nr][nc]로 올 수 있는 모든 경로의 수를 구할 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {
	public static int T, N, M;
	public static int answer = 0;
	public static int[][] arr;
	public static long[][] dp;
    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());
    	
    	arr = new int[N][N];
    	dp = new long[N][N];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	dp[0][0] = 1;
    	
    	for(int i=0;i<N;i++) {

    		for(int j=0;j<N;j++) {
    			if(arr[i][j] == 0) break;
    			
    			//오른쪽으로 이동
    			int nr = i;
    			int nc = j + arr[i][j];
    			
    			if(dp[i][j] > 0 &&  nr >= 0 && nr < N && nc >= 0 && nc < N) {
    				dp[nr][nc] += dp[i][j];	
    			}
        			
        		
        		//아래쪽으로 이동
        		nr = i + arr[i][j];
        		nc = j;
    			if(dp[i][j] > 0 && nr >= 0 && nr < N && nc >= 0 && nc < N) {
    				dp[nr][nc] += dp[i][j];	
    			}
    			
    		} 
    	}
    	
    	System.out.println(dp[N-1][N-1]);
    }
    
}

정답코드2입니다.

아래의 오답코드를 작성하고 확인해보니, 엄청나게 단순한 오류를 찾았습니다.

바로, 해당 칸이 0 일 수 있다는 것 입니다. 만약 0 이라면 계속해서 해당 점을 DFS로 연산을 하겠지요..

아래의 오답코드들이 모두 이 오류떄문에 발생했습니다.

이 코드만 추가해주면 바로 해결됩니다.

if(matrix[r][c] == 0) return 0;

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, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D;
	static long answer = 0;
	static int[][] matrix = new int[101][101];
	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());
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for(int i=0;i<101; i++) {
			Arrays.fill(cache[i], -1);
		}
		
		answer = DFS(0, 0);
		System.out.println(answer);
	}
	
	static long[][] cache = new long[101][101];
	static long DFS(int r, int c) {
		if(r == N-1 && c == N -1) {
			return 1;
		}
		if(matrix[r][c] == 0) return 0;
		if(cache[r][c] != -1) return cache[r][c]; 
		
		long ret = 0;
		int value = matrix[r][c];
		for(int[] dxdr : new int[][] { {1, 0}, {0, 1}} ) {
			int nr = r + value * dxdr[0];
			int nc = c + value * dxdr[1];
			if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
			ret += DFS(nr, nc);
		}
		
		return cache[r][c] = ret;
	}
	
}

오답코드 1 입니다.

시간초과 및 메모리초과 나는 재귀와 메모이제이션을 활용한 코드입니다.

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;
	static long answer = 0;
	static int[][] matrix = new int[101][101];
	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());
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for(int i=0;i<101; i++) {
			Arrays.fill(cache[i], -1);
		}
		
		answer = DFS(0, 0);
		System.out.println(answer);
	}
	
	static long[][] cache = new long[101][101];
	static long DFS(int r, int c) {
//		System.out.println("R:"+r+"C:"+c);
		if(r == N-1 && c == N -1) {
			return 1;
		}
		if(cache[r][c] != -1) return cache[r][c]; 
		
		long ret = 0;
		int value = matrix[r][c];
		for(int[] dxdr : new int[][] { {1, 0}, {0, 1}} ) {
			int nr = r + value * dxdr[0];
			int nc = c + value * dxdr[1];
			if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
			ret += DFS(nr, nc);
		}
		
		return cache[r][c] = ret;
	}
	
}

오답코드2입니다.

오답코드1에서 로직이 너무 복잡해서 그런가 해서 좀 더 간소화했지만, 이제 시간초과는 해결되었지만 메모리초과가 발생합니다.

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, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D;
	static long answer = 0;
	static int[][] matrix = new int[101][101];
	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());
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for(int i=0;i<101; i++) {
			Arrays.fill(cache[i], -1);
		}
		
		answer = DFS(0, 0);
		System.out.println(answer);
	}
	
	static long[][] cache = new long[101][101];
	static long DFS(int r, int c) {
		if(r == N-1 && c == N -1) {
			return 1;
		}
		if(r < 0 || r >= N || c < 0 || c >= N) {
			return 0;
		}
		
		if(cache[r][c] != -1) return cache[r][c]; 
		
		long ret = 0;
		int value = matrix[r][c];
		ret += DFS(r + value, c);
		ret += DFS(r, c + value);
		return cache[r][c] = ret;
	}
	
}

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 10844 쉬운 계단 수 - DP JAVA (0)	2023.08.19
[백준] 2156 포도주 시식 - 동적계획법(DP, Dynamic Programming) JAVA (0)	2023.08.19
[백준] 9465 스티커 - DP JAVA (0)	2023.08.19
[백준] 11055 가장 큰 증가하는 부분 수열 - 동적계획법(Dynamic Programming, DP) + LIBS(Longest Increasing Biggest Subsequence) JAVA (0)	2023.08.19
[백준] 1912 연속합 - DP(동적계획법) + 분할정복(DivideAndConquer) JAVA (0)	2023.08.18

passionfruit200