점프

코드

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#include <stack>
#define ll long long
using namespace std;
ll ans;
int N;
int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};
int board[105][105];
ll dp[105][105];
// dp[r][c] = r행 c열에서 N-1, N-1로 가는 경우의 수 
ll DFS(int r, int c)
{
    if(dp[r][c] != -1) return dp[r][c];
    if(r == N-1 and c == N-1) return 1;
    dp[r][c] = 0;
    for(int d=0;d<2;d++)
    {
        int nr = r;
        int nc = c;
        int len = board[r][c];
        if(len == 0) continue;
        while(len--)
        {
            nr += dr[d];
            nc += dc[d];
        }
        if(nr<0 or nc<0 or nr>=N or nc>=N) continue;
        dp[r][c] += DFS(nr, nc);
    }
    return dp[r][c];
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cin >> board[i][j];
    for(int i=0;i<N;i++)
        fill(dp[i], dp[i]+N, -1);
    ans = DFS(0, 0);
    cout << ans;
    return 0;
}

• 문제 접근
  • DFS를 통해 완전탐색으로 경로 찾기 --> N이 100이라서 너무커서 시간초과가 확실
  • 방향이 증가밖에 없으니 vis없이 BFS를 수행하면 모든 경로의 수를 찾을 수 있을 것이라 생각
    --> N이 작은 경우만 가능 / N이 커지면 시간초과 발생 & 메모리초과 발생
    --> BFS / DFS를 방문체크(vis)없이 수행하면 N에 따라 지수적으로 중복 방문이 늘어나서 메모리 초과가 난다
    (BFS / DFS수행시 특별한 조건이 없는 한 방문체크(vis)는 반드시 있어야 한다는 것을 인지!)
  • 해답 : DFS + DP를 사용해서 풀어야 함!

• 주의
  • 정답의 범위가 2^63-1보다 작거나 같기 때문에 long long 자료형을 써야함 (DFS반환타입도 꼭 바꾸자)