[프로그래머스] 등굣길

등굣길

---

1. 이해하기

• 물에 잠기지 않은 지역을 통해 학교를 가려고 한다. 집에서 학교까지 갈 수 있는 최단 경로의 개수를 1000000007로 나눈 나머지를 반환해야한다.
• DP문제이다.

---

2. 구현하기

• dfs(x,y,d,m,n,map): 현재 위치 x,y, 온 방향 d를 가지고 map크기가 nxm이다.

  • 현재 위치: x,y, 온 방향: d를 모두 가지고 dp에 저장해야 한다. 그렇지 않으면 dp를 더해주는 부분에서 의도치 않은 값이 더해지게 된다.
  • x,y가 가는 방향에 대해서 문제를 풀어주면 된다.

  int dfs(int x, int y, int d, int m, int n, vector<vector<int>>& map) {
      if(x >= n or y >= m) return 0;
      if(map[x][y] == 1) return 0;
      if(x == n-1 and y == m-1) return 1;
      int& ret = cache[x][y][d];
      if(ret != -1) return ret;
      ret = 0;
      ret += dfs(x+1,y,0,m,n,map)%MOD;
      ret += dfs(x,y+1,1,m,n,map)%MOD;
      return ret%MOD;
  }

---

3. 전체 코드

#include <string>
#include <vector>

using namespace std;

int cache[100][100][2];
const int MOD = 1000000007;

int dfs(int x, int y, int d, int m, int n, vector<vector<int>>& map) {
    if(x >= n or y >= m) return 0;
    if(map[x][y] == 1) return 0;
    if(x == n-1 and y == m-1) return 1;
    int& ret = cache[x][y][d];
    if(ret != -1) return ret;
    ret = 0;
    ret += dfs(x+1,y,0,m,n,map)%MOD;
    ret += dfs(x,y+1,1,m,n,map)%MOD;
    return ret%MOD;
}

int solution(int m, int n, vector<vector<int>> puddles) {
    for(int i = 0; i < 100; i++) {
        for(int j = 0; j < 100; j++) {
            cache[i][j][0] = cache[i][j][1] = -1;
        }
    }
    int answer = 0;
    vector<vector<int>> map(n,vector<int>(m,0));
    for(int i = 0; i < puddles.size(); i++) {
        int x = puddles[i][0], y = puddles[i][1];
        x--; y--;
        map[y][x] = 1;
    }
    answer = dfs(0,0,0,m,n,map);
    return answer;
}