등굣길 (프로그래머스)

동적계획법을 사용하는 문제였다.

 

위의 예제를 표로 표현하면 다음과 같다. 이 표는 동적 테이블에 저장될 값들이다.

 

0부터 표현하는 인덱스 특성상 1~4, 1~3 범위를 그대로 표현하기 위해 5 x 4 크기의 배열로 만들었고, 0번째 행열은 값을 모두 0으로 설정하였다. 웅덩이 위치도 0으로 설정하였다. 0이 설정되면 지나 갈 수 없다.

 

이제 집과 물 위치를 제외하고 (x, y) 위치의 값은 (x - 1, y) + (x, y - 1)로 설정해주면 된다. 위 표에서 (1, 2)위치를 예로 들어보자. 위의 값이 1, 왼쪽 값이 0으로 1 + 0 = 1이다. 

 

(2, 4) 위치는 위의 값 1, 왼쪽 값 1로 1 + 1 = 2이다. 이 작업을 학교인덱스까지 해준다. 그러면 다음과 같이 된다.

 

집에서 학교까지 갈 수 있는 방법은 총 4가지이다.

 

코드는 다음과 같다.

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    vector<vector<int>> d(n + 1, vector<int>(m + 1, 1)); // 1로 초기화
    for(int i = 0; i <= n; ++i) d[i][0] = 0; // 0행을 모두 0으로
    for(int i = 0; i <= m; ++i) d[0][i] = 0; // 0열을 모두 0으로
    for(const auto p : puddles) d[p[1]][p[0]] = 0; // 웅덩이 위치에 0값으로 갱신
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            if(i == 1 && j == 1) continue; // 집인 경우는 넘어감
            // 위, 왼쪽 값을 더한다.
            if(d[i][j] != 0) d[i][j] = (d[i - 1][j] + d[i][j - 1]) % 1000000007; 
        }
    }
    return d[n][m];
}