[Programmers] 등굣길

 

 

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

프로그래머스

 

---

 

문제 해결 과정

착안

동적계획법(dynamic programming)을 활용해 문제를 해결하기 위해 시작점으로부터 $i$행 $j$열까지 도달하는 최단경로의 갯수를 저장할 배열 DP[$i$][$j$]을 사용하면, 오른쪽과 아래쪽으로만 이동 가능하므로 DP[$i$][$j$]에 도달하는 방법은

• DP[$i$][$j - 1$]이 웅덩이가 아니면 왼쪽 칸에서 오른쪽 방향으로 이동하여 도달하는 경우가 존재한다.
• DP[$i - 1$][$j$]이 웅덩이가 아니면 위쪽 칸에서 아래 방향으로 이동하여 도달하는 경우가 존재한다.

 

따라서 주어지는 웅덩이를 각각 배열에 표시하고, 위의 을 참고해 학교에 도달하는 최단경로의 개수를 계산한다.

 

구현

편의상, 웅덩이 좌표를 받아 지도에 미리 표시할 때 웅덩이 좌표에 해당하는 칸의 값은 음수(간단하게 -1로 사용)로 표시하여 문제를 해결하였다. 문제에서 주어지는 $m$, $n$의 값이 커질수록 학교에 도달할 수 있는 경우의 수가 크게 증가하므로 int 형 변수에서의 정수 오버플로(integer overflow)를 방지하기 위해 매 단계에서 1000000007로 값을 나눈 나머지를 저장해야 한다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <vector>

#define denom 1000000007

using namespace std;

int DP[101][101];

int solution(int m, int n, vector<vector<int>> puddles)
{   
    DP[1][0] = 1;
    for (vector<int> puddle : puddles)
        DP[puddle[1]][puddle[0]] = -1;
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (DP[i][j] == 0)
            {
                if (DP[i][j - 1] > 0)
                    DP[i][j] += DP[i][j - 1];
                if (DP[i - 1][j] > 0)
                    DP[i][j] += DP[i - 1][j];
                DP[i][j] %= denom;
            }
    
    return DP[n][m] % denom;
}

 

실행 결과