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

dp와 dfs를 활용한 문제이다. 

이 문제와 매우 비슷한 백준 문제가 있으니 다음 문제도 풀어보면 좋다. 

 

[백준 1520번 / C++] 내리막 길

 

거의 똑같은 문제이다. 

 

#접근방법 

1. 집에서 학교에 도착할 때까지 dfs 함수를 호출한다. 
2. 방향은 오른쪽, 아래 방향밖에 없기 때문에 visited 배열 생성하지 않아도 된다. (방문했던 곳에 다시 방문할 일 없음)
3. 처음 방문한 구역에 갈 수 있는 경로의 개수를 메모이제이션 해준다. 
4. 학교에 도착하면 return 1을 해준다. ( 갈 수 있는 경로 하나 있다는 뜻 ) 
5. DP값을 갱신할 때 배열 타입의 범위를 초과하는 예제가 있기 때문에 1000000007로 모듈러 연산을 해서 저장한다. 

 

#include <string>
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll; 
int m,n; 
int map[100][100]; 
int dp[100][100]; 
int dy[2]={0,1}; 
int dx[2]={1,0}; 
int dfs(int y, int x){
    if(y== m-1 && x == n-1){
        return 1; 
    }
    int &ret = dp[y][x]; 
    if(ret!=-1)return ret; 
    ret = 0; 
    for(int i=0; i<2; i++){
        int nx = x + dx[i]; 
        int ny = y + dy[i]; 
        if(ny<0||ny>=m||nx<0||nx>=n||map[ny][nx])continue;    
        ret+=dfs(ny,nx);         
    }
    ret %= 1000000007;
    return ret;     
}

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

 

코딩테스트 연습 - 등굣길