[BOJ/C++] 1890: 점프

🥈 Silver 1

✏️ 1차 솔루션

⭐️ DFS 로 풀이

1. (0,0) 방문처리
2. 현재 위치에서 오른쪽, 아래쪽으로 방문 가능하면 방문 처리하고 DFS로 이동
   1) 현재 위치 이전에 방문한 위치라면 이동할 수 없음
   2) n*n 범위 내에서만 이동할 수 있음
3. 현재 위치의 값이 0 이라면 count 해주고 return

🚨 1차 trouble

시간초과
DP로 풀어야하지만 풀이방법이 떠오르지 않아 DFS로 풀이..

✏️ 2차 솔루션

⭐️ dp 를 0 으로 초기화하고 다음에 갈 수 있는 위치의 dp 값에 현재 dp 값을 더해줌
⭐️ dp 에 해당 위치로 갈 수 있는 가짓수를 저장해두는 것

1. 출발점에서의 가짓수는 1개이므로 dp[0][0]=1 으로 초기화하고 큐에 출발점 좌표 push
2. 현재 위치에서 갈 수 있는 좌표를 큐에 넣어주고 다음에 갈 위치의 dp 값에 현재 위치 dp 값 더해주기
3. 현재 좌표의 값이 0 이라면 큐에서 pop 하기만 하기

🚨 2차 trouble

메모리 초과 ➡️ 큐 사용해서 그런 듯

✏️ 최종 솔루션

⭐️ 큐 대신 for 문으로 처리
오른쪽, 아래쪽으로만 이동가능해서 for 문으로 방문하는 방향과 동일함
➡️ 이전 위치에서 방문 가능한 위치의 dp 값을 미리 갱신해줬기 때문에 for 문으로 방문하면 이전 위치에서 dp 작업이 끝난 이후의 시점일 것
❗️ 하지만 이때 dp 값이 0이라면 이 위치는 방문할 가능성이 없다는 것이므로 dp 값이 0 이 아닌 경우에만 현재 위치에서 방문할 수 있는 위치 dp 갱신해주기
❗️ 같은 원리로 dp[n-1][n-1] 은 for 문으로 방문하는 것보다 먼저 갱신되기 때문에 굳이 방문할 필요 없음

📌 self feedback

for 문으로 모든 위치를 방문하더라도 continue 조건처리해주면 굳이 큐까지 사용하지 않더라도 원하는 위치에 한해서만 처리할 수 있었음

✏️ 최종 code

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    long long board[101][101];
    long long dp[101][101];
    int n;
    cin >> n;
    
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            cin >> board[i][j];
        }
    }
    
    dp[0][0]=1;
    
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            int jump=board[i][j];
            if(jump==0) continue;
            
            if(i<n-1 && i+jump<n) dp[i+jump][j]+=dp[i][j];
            if(j<n-1 && j+jump<n) dp[i][j+jump]+=dp[i][j];
        }
    }
    
    
    cout << dp[n-1][n-1];
    
}