[JAVA] 동적프로그래밍(DP) "등굣길"

https://programmers.co.kr/learn/courses/30/lessons/42898

 

 

• 배열의 초기화

기본타입(Primitive type)의 배열의 경우 초기값을 가지고 있다(int = 0 / String = "") ex) int[] , String

참조타입(Reference type)의 배열의 경우는 엘리먼트의 초기값이 null 임을 주의하자 ex) Integer[]

 

아래링크에서, DP를 사용할때 초기화 스킬을 사용한다는 것에서 아이디어를 얻었다.

2020/10/13 - [코딩테스트/개념정리] - DP(=다이나믹 프로그래밍,Dynamic Programming) 심화

DP(=다이나믹 프로그래밍,Dynamic Programming) 심화

• 가로와 세로길이에 대한 배열

	가로(m)
세 로 (n)	dp테이블	dp테이블
	dp테이블	dp테이블

 

이와 같을 때, for문을 돌리는 상황에서 유의해야한다.

배열 A[i][j]에 대하여,

for(int i = m; ~~~)   for(int j = n; ~~~)

for(int i = n; ~~~)   for(int j = m; ~~~)

두가지를 비교하면, 오른쪽 것이 우리가 가시적으로 생각하는 m*n(가로*세로)의 모양대로 출력 및 입력처리가 될 것이다. 생각해보면 간단하지만, 안쪽에 있는 for문부터 A[i][j] 가 처리되므로 가로의 길이부터 처리되는 것이 맞다.

 

이정도 순서만 지켜주면 출력할때도 원하는 모양대로 출력될 것 이다.

 

---

우선 재귀방식으로 푼 문제풀이부터 보겠다.

 

import java.util.Arrays;

class Solution {
    private static int[][] matrix;

    static int nn, mm;
    public static int solution(int m, int n, int[][] puddles) {
        nn =n; mm =m;
        matrix = new int[n+1][m+1];
        Arrays.stream(puddles).forEach(v -> matrix[v[1]][v[0]] = -1);
        matrix[n][m] = 1;
        return recursive(1,1);
    }

    private static int recursive(int y, int x) {
        if (y > nn || x > mm || matrix[y][x] < 0) return 0;
        if (matrix[y][x] > 0) return matrix[y][x];
        return matrix[y][x] = (recursive(y, x + 1) + recursive(y + 1, x)) % 1000000007;
    }
}

solution 메소드 부터 살펴보면, return recursive(1,1)로 시작지점을 기점으로 리턴한다.

 

이후, recursive메소드에서 점점 값이 증가하면서

point(n. m) = point(n, m -1) + point(n-1, m)

다음과 같은 점화식으로 재귀가 반복된다.

 

 

---

다음은 DP 방식으로 DP테이블을 만들어 업데이트 하는 방식으로 작성한 코드이다.

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n+1][m+1];//dp table
        for(int i=0;i<puddles.length;i++){
            dp[puddles[i][1]][puddles[i][0]]=-1;//웅덩이 -1값
        }

        dp[1][1]=1;//시작지점
        for(int i=1;i<=n;i++){//(1,1)에서 모든 dp테이블 업데이트
            for(int j=1;j<=m;j++){
                if(dp[i][j]==-1){//웅덩이면
                    dp[i][j]=0;//dp테이블값 0
                    continue;
                }
                //웅덩이 아니면
                if(i!=1)    dp[i][j]+=dp[i-1][j]%1000000007;//이전위의값+현재값
                if(j!=1)    dp[i][j]+=dp[i][j-1]%1000000007;//이전왼쪽값+현재값
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }


        return dp[n][m]%1000000007;
    }
}

1	1	1	1
1	0(웅덩이)	1	1+1=2
1	1	1+1=2	2+2=4

 

위의 행부터 아래행으로 내려오면서 차례대로 업데이트 된다.

 

이러한 방식의 업데이트는 길찾기 문제에서도 비슷하게 적용되므로, 일단 손으로 귀납식으로 답추출을 해냈다면, 그 방식을 직관대로 그 방식을 구현하는 것이 맞는 것 같다.