⭐️ DFS
로 풀이
(0,0)
방문처리n*n
범위 내에서만 이동할 수 있음시간초과
DP로 풀어야하지만 풀이방법이 떠오르지 않아 DFS로 풀이..
⭐️ dp 를 0 으로 초기화하고 다음에 갈 수 있는 위치의 dp 값에 현재 dp 값을 더해줌
⭐️ dp 에 해당 위치로 갈 수 있는 가짓수를 저장해두는 것
dp[0][0]=1
으로 초기화하고 큐에 출발점 좌표 push메모리 초과 ➡️ 큐 사용해서 그런 듯
⭐️ 큐 대신 for 문으로 처리
오른쪽, 아래쪽으로만 이동가능해서 for 문으로 방문하는 방향과 동일함
➡️ 이전 위치에서 방문 가능한 위치의 dp 값을 미리 갱신해줬기 때문에 for 문으로 방문하면 이전 위치에서 dp 작업이 끝난 이후의 시점일 것
❗️ 하지만 이때 dp 값이 0이라면 이 위치는 방문할 가능성이 없다는 것이므로 dp 값이 0 이 아닌 경우에만 현재 위치에서 방문할 수 있는 위치 dp 갱신해주기
❗️ 같은 원리로 dp[n-1][n-1]
은 for 문으로 방문하는 것보다 먼저 갱신되기 때문에 굳이 방문할 필요 없음
for 문으로 모든 위치를 방문하더라도 continue 조건처리해주면 굳이 큐까지 사용하지 않더라도 원하는 위치에 한해서만 처리할 수 있었음
#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];
}