[프로그래머스] 3단계 - 등굣길

1. 문제 설명

격자의 크기 m,n 과 물이 잠긴 지역의 좌표를 담은 배열이 주어질 때, 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단 경로의 개수를 return

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

 

 

2. 문제 풀이법

dp 문제이므로 점화식을 도출해야한다

오른쪽과 아래쪽으로만 움직일 수 있으므로 점화식은 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]이다

 

먼저 dp배열을 다 0으로 초기화한 후, 물 웅덩이의 위치는 -1로 초기화한다

출발지인 dp[1][1]은 1로 초기화하고, for문을 돌면서 해당 점화식에 맞게 값을 넣어준다

이때 해당 인덱스가 물 웅덩이가 있는 좌표면 그냥 넘어가고 dp[i - 1][j] 또는 dp[i][j - 1]이 물 웅덩이가 있는 좌표라면 해당 좌표는 0을 더해주면 된다 

 

 

소스 코드

#include <string>
#include <vector>

using namespace std;

int dp[101][101] = { 0 };

int solution(int m, int n, vector<vector<int>> puddles) {
    
    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)
                continue;
            
            int sum = 0;
            
            if (dp[i - 1][j] != -1)
                sum += dp[i - 1][j];
            if (dp[i][j - 1] != -1)
                sum += dp[i][j - 1];
            
            dp[i][j] += sum % 1000000007;
        }
    }
    
    return (dp[n][m]);
}CPP