[프로그래머스/C++] 등굣길

(7/11 - X) 문제를 제대로 이해 못 함

(7/12 - X)

(7/14 - O)

 

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

프로그래머스

 

구현

모든 좌표의 최단 경로의 개수를 dp 테이블에 갱신해 준다.

웅덩이가 있는 좌표는 -1로 넣어 준다.

이동할 수 있는 방법은 오른쪽, 아래이므로 기본적으로 최단 경로는 [x-1][y]와 [x][y-1]을 더한 값으로 계산한다. 위/왼쪽이 막혀 있는(웅덩이 또는 테두리 위치) 경우도 있으므로 아래 경우1234에 따라 계산한다. 막혀 있음은 -1로 표기한다.

• 경우1. 왼쪽, 위쪽 모두 막혀 있는 경우 - 갈 수 있는 방법이 0이다.
• 경우2. 왼쪽이 막혀 있는 경우 - 위쪽에서만 올 수 있으므로, 위쪽에서 올 수 있는 경로 개수를 더한다.
• 경우3. 위쪽이 막혀 있는 경우 - 왼쪽에서 올 수 있는 경로 개수를 더한다.
• 경우4. 위/왼쪽에서 모두 올 수 있는 경우 - 위/왼쪽의 경로 개수를 모두 더한다.

계산한 최단 경로 개수에 1,000,000,007를 나머지 연산 해서 dp 테이블에 넣어 준다.

 

 

실수

!좌표 반전!

 

 

 

코드

// 프로그래머스 고득점kit 동적계획법 - 등굣길
// (7/11 - X) 틀림
// (7/12 - X)
// (7/14 - )
#include <string>
#include <vector>

using namespace std;

int dp[101][101];
int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    for (int i = 0; i < 101; i++) {
        dp[0][i] = -1;
        dp[i][0] = -1;
    }

    dp[1][1] = 1;

    for (vector<int>& v : puddles) {
        dp[v[1]][v[0]] = -1;
    }


    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) continue; // 시작 좌표
            if (dp[i][j] == -1) continue; // 웅덩이
            if (dp[i][j - 1] == -1 && dp[i - 1][j] == -1) { // 경우4
                dp[i][j] = 0;
            }
            else if (dp[i][j - 1] == -1) { // 경우2
                dp[i][j] = dp[i - 1][j] % 1'000'000'007;
            }
            else if (dp[i - 1][j] == -1) { // 경우3
                dp[i][j] = dp[i][j - 1] % 1'000'000'007;
            } 
            else { // 경우4
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1'000'000'007;
            }
        }
    }
    
    answer = dp[n][m] ;

    return answer;
}
int main() {
    vector<vector<int>> v = { {2,2} };
    solution(4, 3, v);
}