[프로그래머스LV3] 등굣길 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/42898?language=cpp

프로그래머스

 

이 문제를 처음 풀었던 2023년 5월에도 bfs로 풀면 되지 않을까 생각했고 무려 2024년 10월에도 같은 생각을 해서 틀렸다는 점에서 반성이 필요하다. 동적계획법을 보고 다익스트라여서 dp라고 한건가 생각했는데 아니었다.

 

100 * 100 이고 아무리 다익스트라를 사용한다 해도 결국은 2^100*100 이 되어버린다.

 

그래서 이 문제는 그냥 dp로 중복을 제거하여야한다.

 

dp에 어떤 정보를 담아야할까? 난 처음에 이 경로를 따라갔을 때 목적지까지 가는 경로인지 아닌 경로인지 확인해보려 했다. 그러나 이 방법은 결국은 끝까지 갔다가 백트래킹으로 돌아와야하고 이는 모든 경로를 보는 것 까지는 아니지만 그래도 많은 시간이 소요된다.

 

그래서 이 DP[i][j] 에는 i, j까지 도달할 수 있는 경우의 수 를 넣어놓아야한다.

 

그림으로 표현해보자.

 

각 자리의 숫자는 그 자리에 도달할 수 있는 최단거리 방법이다. 선으로 까지 표현해보면

 

 

좀 복잡하지만 2,2 자리를 보면 많은 선이 지나가지만 결국은 위에서 오는 것과 왼쪽에서 오는 것 두가지 방법으로 올 수 있기 때문에 다음과 같이 2이다.

 

그리고 각 자리수는 자리수[i][j] = 자리수[i - 1][j] + 자리수[i][j - 1] 임을 알 수 있다!

 

이것을 DP로 표현하면

 

DP[i][j] = DP[i - 1][j] + DP[i][j - 1]

 

이렇게 나오고 Top-Down 방식을 사용해야함을 알 수 있다. M, N 에서 시작하다보면 결국은 0,0 까지 갈 것이고 0,0 부터 return 1 을 진행하면 된다.

 

이 때 반복문만을 사용할수도 있고 DFS를 사용할 수도 있다. 여기선 DFS로 진행해보았다. 일반 반복문으로 구현해도된다. 확실히 눈치가 빠르면 쉽게 풀 수 있는 문제였다. 결국은 왼쪽과 위에서만 오니까 

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

bool wator[101][101];
int dp[101][101];

int dfs(int row, int col){
    if(row < 0 || col < 0) return 0;    
    if(wator[row][col]) return 0;
    if(dp[row][col] != 0) return dp[row][col];
    
    return dp[row][col] = (dfs(row - 1, col) + dfs(row, col - 1)) % 1000000007;
}

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    dp[0][0] = 1;
    for(vector<int> v : puddles){
        wator[v[0] - 1][v[1] - 1] = true;
    }
    
    answer = dfs(m - 1, n - 1);
    
    return answer;
}