99클럽 코테스터디 40일차 TIL 프로그래머스- 등굣길

등굣길

프로그래머스 Level 3 DP
문제 링크

프로그래머스

 

문제 설명

배열이 주어지고, 시작점은 1,1 끝점은 n,m 일 때
중간에 갈 수 없는 지점이 있고,
시작점으로부터 끝점까지 도달할 수 있는 최단 경로의 갯수를 구하면 되는 문제

문제 풀이

Buttom-Up 방식으로 풀이했다.
puddles 에 주어지는 부분들은 미리 -1로 처리했고
해당 부분을 만나면 0으로 처리해주며 진행했다.

코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int dp[101][101];

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    for (int i=0; i<puddles.size(); i++) {
        dp[puddles[i][1]][puddles[i][0]] = -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;
            } else {
                int a=0, b=0;
                if (dp[i-1][j] != -1) {
                    a = dp[i-1][j];
                }
                if (dp[i][j-1] != -1) {
                    b = dp[i][j-1];
                }
                dp[i][j] += (a+b)%1000000007;
            }
        }
    }

    return dp[n][m];
}

파이썬 코드

def solution(m, n, puddles) -> int:
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for li in puddles:
        dp[li[1]][li[0]] = -1

    dp[1][1] = 1

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if dp[i][j] == -1:
                dp[i][j] = 0
                continue
            if dp[i-1][j] != -1:
                dp[i][j] += dp[i-1][j]
            if dp[i][j-1] != -1:
                dp[i][j] += dp[i][j-1]
            dp[i][j] %= 1000000007

    return dp[n][m]

회고

DP 는 해도해도 적응이 안되는 것 같다.