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

programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

웅덩이를 피해서 목적지까지의 경로의 수를 세야 한다.

다른 분들은 DP를 이용해서 쉽게 풀었지만, 나는 DP+DFS로 풀었다.

 

#include <string>
#include <vector>
#define MOD 1000000007

using namespace std;

int dp[101][101], arr[101][101], N, M, xmove[2] = {1, 0}, ymove[2] = {0, 1};

int DFS(int startX, int startY){
    if(dp[startX][startY] != -1){
        return dp[startX][startY];
    }
    if(startX == N && startY == M)
        return 1;
    
    dp[startX][startY] = 0;
    
    for(int i = 0 ; i < 2 ; i++){
        int nx = startX + xmove[i];
        int ny = startY + ymove[i];
        
        if(nx >= 1 && nx <= N && ny >= 1 && ny <= M){
            if(arr[nx][ny] == 1){
                dp[startX][startY] += (DFS(nx, ny) % MOD);
            }
        }
    }
    return dp[startX][startY] % MOD;
}

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    N = n;
    M = m;
    
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= m ; j++){
            dp[i][j] = -1;
            arr[i][j] = 1;
        }
    }
    
    for(int i = 0 ; i < puddles.size() ; i++){
        int x = puddles[i][1];
        int y = puddles[i][0];
        arr[x][y] = 0;
    }
    
    answer = DFS(1,1);
    
    return answer;
}

일단 DFS를 하기 위해 arr배열을 모두 1로 초기화해주었고, DP 배열은 -1로 초기화해주었다. (미방문은 -1, 방문은 n)

또한 puddles의 원소들을 통해 방문 못하는 x, y를 arr배열에 0으로 업데이트해주었다.

 

그러고 나서 1,1부터 DFS로 그래프 순환을 해주었는데, 여기서 DP개념을 이용했다.

만약 매번 경로를 찾기 위해 백트래킹을 이용해서 모두 세면 너무나도 많이 탐색을 해야 한다.

따라서 특정 x, y까지 방문할 수 있는 경우의 수를 dp배열에 저장해두어서 만약 이미 탐색이 끝난 곳을 방문했다면 그 배열에 저장되어있는 경로의 수를 더해준다.

 

그렇게 탐색을 하다가 목표인 M과 N에 도착하면 1을 리턴해주는데, dp[startX][startY] += DFS(nx, ny)에서 볼 수 있듯이 현재 지점에서 목표 지점까지의 경우의 수를 누적해서 저장해준다.

또한, 더 이상 방문할 곳이 없다면 현재 dp의 값을 반환해준다.

그래서 결과적으로

4	3	3	1
1	-1	2	1
1	1	1	-1

이 완성된다. (도착점에 도착하면 1을 반환하면서 역순으로 경로에 더해간다.)