프로그래머스 등굣길

문제

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

코드

cpp

#include <string>
#include <vector>

#define N 1000000007
using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    vector<vector<int>> dp(n,vector<int>(m,0));
        
    for(auto i: puddles)
        dp[i[1]-1][i[0]-1]=-1;
    
    dp[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if((i==0&&j==0)||dp[i][j]==-1) continue;
            
            if(dp[i-1][j]==-1||i==0) dp[i][j]=dp[i][j-1];
            else if(dp[i][j-1]==-1||j==0) dp[i][j]=dp[i-1][j];
            else dp[i][j]=dp[i-1][j]%N+dp[i][j-1]%N;  
        }
    }
    answer=dp[n-1][m-1]%N;
    return answer;
}

python

def solution(m, n, puddles):
    answer = 0
    dp = [[0]*(m+1) for _ in range(n+1)]
    dp[1][1] = 1
    for x, y in puddles:
        dp[y][x] = -1
    for i in range(1, n+1):
        for j in range(1, m+1):
            if dp[i][j] == -1:
                dp[i][j] = 0
                continue
            if i == j == 1:
                continue
            dp[i][j] = dp[i-1][j]+dp[i][j-1]

    return dp[n][m]%1000000007

풀이

집의 위치는 (1,1)로 고정되있고 학교의 위치는 (m,n)으로 고정되있을 때 집에서 학교까지 가는 최단경로의 수를 구하는 문제입니다. 개인적으로 n,m위치가 바뀐게 좀 불편했습니다

집에서 출발해서 오른쪽과 아래쪽으로만 움직이면 항상 최단경로이고 물웅덩이 예외처리를 해주면 문제는 어렵지 않게 풀 수 있습니다

코드를 보시면 물웅덩이는 -1로 표시해서 예외처리를 해주고 (0,0)에 1을 넣어준 다음 이중for문으로 dp테이블을 돌면서 만약 위쪽에 물웅덩이가 있거나 i가 0이라면 왼쪽값을 복사하고 왼쪽에 물웅덩이가 있거나 j가 0이라면 위 값을 복사합니다. 그게 아니라면 위의 값과 왼쪽값을 1,000,000,007로 나눠주면서 더해주면 됩니다.