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

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

프로그래머스

 

난이도 : Level 3 
알고리즘 유형 : DP 
풀이 시간 : 17분 

문제 풀이 

전형적인 2차원 DP문제라고 생각한다. 문제에서 경로는 오른쪽으로 이동, 아래로 이동 두 가지만 존재하고, (1, 1)에서 (N, M)으로 이동할 수 있는 모든 경로를 찾는 문제이다. 중간에 물웅덩이가 있는데, 이 부분으로는 이동할 수 없다. 

사실 격자의 크기가 $N ≤ 100$, $M ≤ 100$으로 주어졌기 때문에 BFS로도 충분히 풀 수 있을 것 같지만, DP로 접근해보도록 하겠다. DP로 접근하면 $O(NM)$에 풀 수 있다.

모든 이동경로를 찾는 문제이기 때문에 현재 좌표로 올 수 있는 이전 좌표들의 경우의 수 합으로 업데이트를 해주어야 한다. 이를 코드로 나타내면 다음과 같다. 

dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000007;

본 문제에서 최단경로의 개수를 $1000000007$로 나눈 나머지에 대해 구하라고 하였기 때문에, 최단경로를 업데이트 할 때마다 나머지값으로 업데이트를 진행하였다.

또한, 2중 반복문을 돌며, 물웅덩이를 만나는 경우에는 `continue`처리를 하여 다음 결과에 $0$값이 오도록 하였다. 

 

코드

/*
일부 지역이 물에 잠김
물에 잠기지 않은 지역을 통해 학교를 가려고 한다.
우, 하 로만 이동 가능함
물이 잠긴 지역의 좌표는 주어진다.
*/

#include <string>
#include <vector>

using namespace std;

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

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    for (int i=0;i<puddles.size();i++){
        grid[puddles[i][1]][puddles[i][0]] = 1;
    }
    
    // dp 시작
    dp[0][1] = 1;	// 0번 줄의 값들은 0으로 초기화 되어있기 때문에 시작 위치를 1로 업데이트 해주기 위한 초기화 진행
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (grid[i][j]) continue;
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000007;
            // printf("%d\n", dp[i][j]);
        }
    }
    
    answer = dp[n][m];
    return answer;
}

배운 점 

간단한 DP로 해결할 수 있었던 문제이다. 이전에 DP문제를 꽤 접해봤던 경험치가 쌓여서 이런 문제는 이제 쉽게 해결되지 않았나 싶다 ㅎㅎ!