[프로그래머스 lv3] 등굣길 풀이

해설

오른쪽과 아래쪽으로 이동하고, 특정 지점을 향하는 문제는 dp의 전형적인 유형이다.

 

dfs(int x, int y) 를 (x, y)에서 (n, m)까지 이동하는 경우의 수라고 정의할 때 이동할 수 있는 방법은 두 가지가 있다.

1) 오른쪽 방향: (x, y+1)에서 (n, m)으로 이동하는 방법

2) 아래쪽 방향: (x+1, y)에서 (n, m)으로 이동하는 방법

따라서, dfs(x, y)는 dfs(x, y+1) + dfs(x+1, y) 로 정의할 수 있다.

 

이때, 메모이제이션 없이 dfs를 돌려버리면 TLE가 발생할 가능성이 높으므로 이미 구한 값을 저장해놓고 해당 결과가 필요할 때마다 찾아 쓰는 동적프로그래밍 방법을 사용하자.

dfs(int x, int y)가 실행되었을 때, 그 결과가 이미 memo[x][y]에 저장되어있다면 별다른 계산 없이 memo[x][y]를 리턴하는 것이다.

 

정리해보면, dfs(int x, int y)에 대하여,

1) x = n, y = m 일 때, (n, m)에서 (n, m)으로 가는 방법은 한개 뿐(자기 자신에서 자기 자신으로 이동) 이므로 1을 리턴한다.

2) 이미 구한 결과가 memo[x][y]에 저장되어있다면 별도의 재귀 호출 없이 memo[x][y]를 리턴한다.

3) 나머지 경우, dfs(x, y+1) + dfs(x+1, y) 를 구하여 리턴한다.

 

문제에서 (1, 1) 부터 (n, m)까지의 경우의 수를 리턴하라고 했으므로 dfs(1, 1) 값을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int board[105][105];
int memo[105][105];

int dfs(int x, int y, int n, int m) {

    if (x == n && y == m) return 1;
    if (memo[x][y]) return memo[x][y];

    long long re = 0;
    if (y+1 <= m && !board[x][y+1]) re += dfs(x, y+1, n, m);
    if (x+1 <= n && !board[x+1][y]) re += dfs(x+1, y, n, m);
    memo[x][y] = re%1000000007;
    return memo[x][y];
}

int solution(int m, int n, vector<vector<int>> puddles) {

    for (auto v : puddles) 
        board[v[1]][v[0]] = 1;
   return dfs(1, 1, n, m);
}