[JAVA] DP : 등굣길

1. 문제 내용

요약
시작점과 끝점까지의 최단경로의 갯수 구하기
단, 입력값으로 중간에 길이 막혀있는 경우도 있다

2. 접근방법
 최단경로를 구하기위해 DP를 이용해봤다.
DP를 이용해 이미 방문했던 좌표를 판단하여 그 이후는 탐색을 하지않고 값을 가져오는 과정을 거쳐 해결하면 될 것 같다

3. 구현과정
 처음에 재귀호출을 통해 구현을 해보았는데 코드는 아래와 같다

int[][] dp = new int[n][m];
dp[n-1][m-1] = 1;
for(int i = 0; i < puddles.length; i++){
	dp[puddles[i][1] - 1][puddles[i][0] - 1] = -1;
}
int result = mapping(dp, 0, 0, n, m);

일단 탑다운DP를 사용했기 때문에 배열의 마지막위치를 1로 초기화를 하고 물웅덩이의 위치를 -1로 초기화해주었다
그외에는 0으로 자동초기화 된다

public int mapping(int[][] dp, int x, int y, int n, int m){
    if(dp[x][y] >= 1){
        return dp[x][y];
    }
    if(y + 1 < m){
        if(dp[x][y+1] != -1)
            dp[x][y] += mapping(dp, x, y+1, n, m);
        }
    if(x + 1 < n){
        if(dp[x+1][y] != -1)
            dp[x][y] += mapping(dp, x + 1, y, n, m);
        }
    return dp[x][y];
}

mapping 메서드를 작성해 배열의 마지막에 닿으면 리턴하여 본격적으로 값을 삽입하기 시작한다
그리고 해당 좌표와 연결되어있던 루트들에서 도착지까지의 값들을 계속 받고 만약 값을 한번이라도 변경했다면 그 값 그대로 반환하도록 했다

그렇게 제출을 했는데

  이런 결과가 나왔다
출력은 재대로 되는데 무엇이 문제인가 찾아보다 재귀호출을 사용했을 경우 메모리부족으로 효율성이 떨어질 수 있어서 반복문을 통해 구현하면 해결될 수도 있다는 정보를 구했다
그래서 로직그대로 반복문으로 변경해보았고

아래와 같이 작성하였다

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n][m];

        dp[n - 1][m - 1] = 1;

        for (int[] puddle : puddles) {
            if (puddle[1] - 1 < n && puddle[0] - 1 < m) {
                dp[puddle[1] - 1][puddle[0] - 1] = -1;
            }
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                if (dp[i][j] == -1) {
                    dp[i][j] = 0;
                    continue;
                }

                if (j + 1 < m && dp[i][j + 1] != -1) {
                    dp[i][j] = (dp[i][j] + dp[i][j + 1]) % 1000000007;
                }

                if (i + 1 < n && dp[i + 1][j] != -1) {
                    dp[i][j] = (dp[i][j] + dp[i + 1][j]) % 1000000007;
                }

                if (i == 0 && j == 0) {
                    continue;
                }
            }
        }

        return dp[0][0];
    }
}

 

4. 결과

해결된듯하다
근데 이러한 문제를 격어보니 재귀 호출에 대한 공부가 더 필요할 것 같다
재귀호출의 장점과 반복문의 장점을 좀 찾아보면서 알맞게 사용하는 법을 더 익혀봐야겠다