등굣길 - 프로그래머스

문제

문제 난이도 : 3단계

문제 분류 : 다이나믹 프로그래밍

문제 리뷰

저번에 풀어본 문제와 비슷하고 그것보다 쉬워서 금방 풀었다.

만약 BFS 같은 탐색을 사용하였다면, 조합이 폭발적으로 상승해서 시간 초과나 메모리 초과가 뜨지 않았을까 싶다.

초등학교 때 배웠던 경우의 수 개념을 사용하면 좋은 문제이다.

1. Base Case로 DP[1][2 ~ N]과 DP[2 ~ N][1]를 처리해준다. 한 가지 밖에 없거나, 가는 길에 개울이 있다면 0이 된다.
2. DP[i][j]는 j,i로 가는 경우의 수를 저장한다.
   DP[i][j]로 오는 방법은 DP[i-1][j] + DP[i][j-1] 이므로 이를 사용하면 되고, 만약 개울이 있다면 0으로 처리한다.

문제 소스코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int DP[101][101];

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    DP[1][1] = 1;
    vector<vector<bool>> Map(n+1, vector<bool>(m+1));
    for(vector<int> v: puddles){
        Map[v[1]][v[0]] = true;
    }
    for(int i = 2; i <= m; i++){
        if(DP[1][i - 1] != 0) DP[1][i] = 1;
        if(Map[1][i] == true) DP[1][i] = 0;
    }
    for(int i = 2; i <= n; i++){
        if(DP[i-1][1] != 0) DP[i][1] = 1;
        if(Map[i][1] == true) DP[i][1] = 0;
    }
    
    
    
    for(int i = 2; i <= n; i++){
        for(int j = 2; j <= m; j++){
            if(Map[i][j] != true){
                DP[i][j] = DP[i-1][j] + DP[i][j-1];
            }
            DP[i][j] %= 1000000007;
        }
        
        
    }
    answer = DP[n][m];
    
    return answer;
}