[프로그래머스] 등굣길 (Java)

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

프로그래머스

 

 

Review

오랜만의 코테 공부...

처음에 헷갈렸던 포인트는 m과 n을 반대로 설정했다는 것.. 그냥 문제의 그림을 돌려서 좌표로 생각하면 된다! 만약 문제가 좌표로 나왔다면 m과 n을 그대로 설정하면 된다. 그래도 한 번 틀려봤으니 다음에는 어떻게 풀어야 할지 잘 판단할 수 있을 것 같다.

그리고 DFS로도 풀 수 있을 것 같아서 풀어봤다.

 

 

Code

DP ver.)

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        final int MOD = 1000000007;
        
        int[][] dp = new int[n + 1][m + 1];
        boolean[][] isPuddle = new boolean[n + 1][m + 1];
        
        for (int[] puddle : puddles) {
            isPuddle[puddle[1]][puddle[0]] = true;
        }

        dp[1][1] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (i == 1 && j == 1) {
                    continue;
                }
                if (isPuddle[i][j]) {
                    dp[i][j] = 0;
                }
                else {
                    dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
                }
            }
        }

        return dp[n][m];
    }
}

 

DFS ver.)

public class Solution {
    final int MOD = 1000000007;
    int[][] dp;
    boolean[][] isPuddle;
    
    public int solution(int m, int n, int[][] puddles) {
        dp = new int[n + 1][m + 1];
        isPuddle = new boolean[n + 1][m + 1];

        for (int[] puddle : puddles) {
            isPuddle[puddle[1]][puddle[0]] = true;
        }

        return dfs(1, 1, m, n);
    }

    private int dfs(int x, int y, int m, int n) {
        if (x == m && y == n) {
            return 1;
        }
        
        // 이미 계산된 값이 있으면 반환
        if (dp[y][x] != 0) {
            return dp[y][x];
        }
        
        // 웅덩이 있는 곳은 경로 없음, 0 반환
        if (isPuddle[y][x]) {
            return 0;
        }
        
        int right = 0, down = 0;
        if (x < m) {
            right = dfs(x + 1, y, m, n);
        }
        if (y < n) {
            down = dfs(x, y + 1, m, n);
        }

        dp[y][x] = (right + down) % MOD;

        return dp[y][x];
    }
}