프로그래머스. 등굣길(c++) / DP+BFS or DP+DFS

1) DP+BFS

BFS와 DP를 모두 활용해서 푸는 문제였다.

약간 백준에서 욕심쟁이 판다?와 비슷한 느낌? 하지만 이 문제가 훨~~씬 쉽다.

 

[메인 로직]

일단, dp[y][x] = dp[y-1][x] + dp[y][x-1]이라는 공식은 문제를 읽어보면 쉽게 세울 수 있다.

이것을 응용해서 특정 칸에서 다음 칸으로 이동하게 되면, 다음 칸의 dp값에 현재 칸의 dp값을 무조건 더해주었다. 지나가는 길이기 때문에 경로추가! (dp[ny][nx] += dp[y][x])

또한!!! 이미 방문한 곳은 큐에 절대로 넣어주지 않았다... 왜냐하면 수가 배가 되기 때문에....dp값은 방문했던 곳이여도 지나가는 길에 도달한 것이기 때문에 항상 더해주었지만, 이미 방문한 점은 다시 큐에 넣어주면 안된다!

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
 
using namespace std;
 
int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    int map[101][101] = {0, };
    long long dp[101][101] = {0, };
    int visited[101][101] = {0, };
    int dirX[2] = {0, 1};
    int dirY[2] = {1, 0};
    
    for(int i=0; i<puddles.size(); i++){
        // 물에 잠긴곳 -1로 표시
        map[puddles[i][0]][puddles[i][1]] = -1;
    }
    
    queue<pair<int, int>> q;
    q.push(make_pair(1, 1));
    dp[1][1] = 1;
     
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        visited[y][x] = 1;
        q.pop();
        
        if(y==m && x==n){
            break;
        }
        
        for(int i=0; i<2; i++){
            int ny = y+dirY[i];
            int nx = x+dirX[i];
            if(1<=ny && ny<=m && 1<=nx && nx<=n){
                if(map[ny][nx]==-1) continue;
                dp[ny][nx] += (dp[y][x]%1000000007);
                // 더해주는 건 다 더해주고, 큐에 넣는 것은 한 번만!
                if(visited[ny][nx]) continue;
                visited[ny][nx] = 1;
                q.push(make_pair(ny, nx));
            }
        }
    }
    
    answer = dp[m][n]%1000000007;
    
    return answer;
}

2) DP+DFS

어떻게 보면, 가장 정석적인 방법? 이라고 생각된다.

다시 복습하면서 풀어보았는데 이번에는 DP+DFS방법이 문득 생각나서 이렇게 풀었다.

 

#include <string>
#include <vector>
#include <climits>
#include <cstring>
#include <iostream>
 
using namespace std;
 
int dp[101][101] = {0, };
 
int dfs(int x, int y){
    if(dp[x][y]!=-1){
        return dp[x][y];
    }
    
    dp[x][y] = (dfs(x-1, y)+dfs(x, y-1))%1000000007;
    
    return dp[x][y];
}
 
int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    memset(dp, -1, sizeof(dp));
    
    for(int i=1; i<=n; i++){
        dp[1][i] = 1;
    }
    
    for(int i=1; i<=m; i++){
        dp[i][1] = 1;
    }
    
    for(int i=0; i<puddles.size(); i++){
        int x = puddles[i][0];
        int y = puddles[i][1];
        if(x==1){
            for(int j=y; j<=n; j++){
                dp[1][j] = 0;
            }
        }
        if(y==1){
            for(int j=x; j<=m; j++){
                dp[j][1] = 0;
            }
        }
        dp[x][y] = 0;
    }
    
    dp[m][n] = (dfs(m-1, n) + dfs(m, n-1))%1000000007;
    
    answer = dp[m][n];
    
    return answer;
}