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

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

 

등굣길 보통 이런문제는 상하좌우, 좌표 경우의수 최단거리로 보통 잘 나오는 문제이다.

그래서 처음에 보자마자 최단거리의 경우의 수를 찾으려고 했다. 하지만 문제에서 방향은 오른쪽과 아래로만 이동이 가능하다. 즉, 목적지에 도달하기만 한다면 모두 최단거리라는 뜻이다.

 이러한 문제는 완전탐색을 할 필요없이 dp를 활용하여 sum누적방식으로 좌표값을 계산하고 최종 마지막 도착지의 인덱스값을 리턴하면 대부분 해결된다. 물론 웅덩이같은 제한조건은 잘 생각하여, 피해갈 수 있도록하고, 범주내에서만 이동할수 있도록 신경써주면 쉽게 풀 수 있다.

 

---

프로그래머스

 

문제 풀이 설명 (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

프로그래머스