(프로그래머스 c++)등굣길

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    int check[101][101] = {0, };
    int visited[101][101] = {0, };
    
    for(int i = 0; i < puddles.size(); i++)
        check[puddles[i][1]][puddles[i][0]] = -1;
    
    visited[1][0] = 1;
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(check[i][j] == -1)
                visited[i][j] = 0;
            else
                visited[i][j] = (visited[i - 1][j] + visited[i][j - 1]) % 1000000007;
        }
    }
    return visited[n][m];
}

DP 방법으로 문제를 풀었다.

우선 check와 visited 배열을 선언한다.

check는 물 웅덩이의 위치를 확인하기 위한 배열,

visited는 목표 지점까지 경로의 수를 저장하기 위한 배열이다.

 

먼저 물 웅덩이가 있는 위치를 -1로 저장한다.

그리고 시작 위치의 값을 1로 저장하고 경로를 탐색한다.

이중 for문을 이용하여 웅덩이가 있는 위치는 0으로,

웅덩이가 아닌 곳은 visited[i - 1][j] + visited[i][j - 1]을 해주고 바로 1000000007로 나누어준다.

 

이렇게 하면 DP로 visited[n][m]까지의 최단 경로의 수를 구할 수 있다.