[프로그래머스 / Level 3] 등굣길 (C++)

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

코딩테스트 연습 - 등굣길

해당 좌표까지 갈 수 있는 경우의 수들을 합쳐서 풀 수 있는 문제입니다.

 

문제 접근법

• 시작점을 기준으로 오른쪽 아래쪽으로만 움직일 수 있으므로, 시작점 모든 우측열과 시작점 모든 아래행을 1로 체크한다.
• 시작점 모든 우측열과 아래행을 확인하며 물이 발견시 그 부분부터 모든 부분을 0으로 바꾸어준다.
• 오른쪽과 아래쪽만으로 움직일 수 있으므로, 도착지 기준 좌측과 위쪽의 경우의 수 값을 더해주면서 진행한다.

아래는 코드입니다.

#include <string>
#include <vector>
 
using namespace std;
 
int dp[101][101];
bool water[101][101];
 
int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    int len = puddles.size();
    
    for(int i = 1; i <= 100; i++)
    {
        dp[1][i] = 1;
        dp[i][1] = 1;
    }
    
    for(int i = 0; i < len; i++)
        water[puddles[i][1]][puddles[i][0]] = true;
    
    for(int i = 1; i <= m; i++)
        if (water[1][i])
            for (; i <= m; i++)
                dp[1][i] = 0;
    
    for(int i = 1; i <= n; i++)
        if (water[i][1])
            for (; i <= n; i++)
                dp[i][1] = 0;
    
    for(int i = 2; i <= n; i++)
        for(int j = 2; j <= m; j++)
            if(!water[i][j])
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000007;
 
    return answer = dp[n][m];
}