[프로그래머스] 42898 : 등굣길 [JAVA] Lv.3

프로그래머스

 

문제 풀이 설명 (summary)

• 완전 탐색을 하려고 생각할 수도 있으나, 경우의 수가 너무 커져 시간초과로 실패할 수 있다.
• 그래서, DP를 활용해서 좌표마다 누적해서 원하는 목적지의 좌표 값을 구한다.
• 또한 (오른쪽, 아래)로만 이동하기 때문에 최단거리로 가는건 고려하지 않아도 된다.
• 목적지에 도착하는 거리는 도착하면 모두 동일하다. 

 

문제 풀이 접근법

• 정형화된 그리드 경로 문제는 BFS보다 DP가 훨씬 효율적입니다.
• BFS는 주로 최단거리 혹은 가중치가 있는 경로 탐색에 적합합니다.
• 현재 문제에서는 단순 경로 수 계산 문제이기 때문에, DP 방식이 시간적으로 훨씬 효율적인 것입니다.

 

풀이 코드 (Code)

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        int m = 4;
        int n = 3;
        int[][] puddles = {{2,2}};

        System.out.println(solution(m,n,puddles));
    }

    private static int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n + 1][m + 1];

        for (int[] puddle : puddles) {
            int x = puddle[0];
            int y = puddle[1];
            dp[y][x] = -1; // 웅덩이
        }

        dp[1][1] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (dp[i][j] == -1) {
                    dp[i][j] = 0;
                    continue;
                }
                if (i > 1) dp[i][j] += dp[i - 1][j];
                if (j > 1) dp[i][j] += dp[i][j - 1];
                dp[i][j] %= 1_000_000_007; // 모듈로 연산
            }
        }

        return dp[n][m];
    }
}

 

문제 링크 (Link)

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