[Programmers]#Level3_등굣길, DP

#1. 문제

프로그래머스

 

---

 

#2. 풀이

 

1. DP

[알고리즘]#5_동적 계획법

동적 계획법은 주어진 입력 크기에 따라 하위 문제를 재귀적으로 해결하고, 그 결과 값을 기억함으로써 중복 계산을 방지하는 최적화 기법입니다. 일반적으로, Memoization을 위한 데이터 목록이 필요하고, DFS를 통해 구현되는 경우가 많습니다.

 

2. DFS 하면 시간 초과! DP 하면 풀 수 있다!

dp[i][j] = dp[i-1][j] + dp[i][j-1],
if dp[i][j] != IsPuddle (물 웅덩이 지역이 아닐 경우), 그리고 i-1 > 0, j-1 > 0 일 경우.

1. 미로 유형의 문제와 비슷해 보여, DFS를 적용하면 시간 초과가 발생합니다. 따라서, DP 활용을 고려하여 점화식을 세웁니다.
2. 위 점화식을 기반으로 DP를 수행하고, 결과 값을 1000000007로 나누어 나머지 값을 저장합니다.

 

---

 

#3. 코드

/* 
    @문제 : 집에서 물에 잠기지 않은 지역을 통해 학교까지 가는 최단 경로의 개수 %  1,000,000,007
    @설명
            1. 점화식 : dp[i][j] = dp[i-1][j] + dp[i][j-1], 아래 3조건을 만족할 경우.

            조건1 : if dp[i][j] 지역이 물웅덩이가 아닐 때
            조건2 : if i-1 > 0, dp[i][j] += dp[i-1][j]
            조건3 : if j-1 > 0, dp[i][j] += dp[i][j-1]
*/

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    
    //물웅덩이 목록, true 일 경우 물웅덩이 존재!
    vector<vector<bool>> IsPuddle(n+1, vector<bool>(m+1, false));
    for(int i=0; i<(int)puddles.size(); ++i)
    {
        IsPuddle[puddles[i][1]][puddles[i][0]] = true;
    }

    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    // 시작점 = 1
    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])
            {
                // 위쪽 지역
                if(i-1 > 0)
                {
                    dp[i][j] += dp[i-1][j];
                }
                // 왼쪽 지역
                if(j-1 > 0)
                {
                    dp[i][j] += dp[i][j-1];
                }
                dp[i][j] %= 1000000007;
            }
        }
    }

    return dp[n][m];

}

 

---