[BaekJoon/백준] 1890번 점프

 

 

경로의 개수는 2^63-1보다 작거나 같다.

•  경로 DP값은 int로는 못 담는다.
• dfs bfs 같은 탐색으론 불가능하다.

 

Dynamic Programming (동적 계획법)을 이용해야 한다.

 

나 근데 DP 왜이렇게 못해졌지 ㅜ.ㅜ

한시간 붙잡고 못 풀어서 해설을 찾고 도움을 받았다.

 

 

DP 풀이 방법에는 본래 두 가지가 있는데 

1. 재귀 + 메모이제이션 = Top down
2. 반복문 + 타뷸레이션 = Bottom up

두 가지 다 이용해 볼 것이다.

 

각 방법에서 DP[i][j]의 의미는 이러하다.

1. 메모이제이션 : 해당 위치에서 목적지까지 가는 경로 수

2. 타뷸레이션 : 해당 위치까지 가는 경로 수 

 

 

메모이제이션

메모이제이션 문제를 풀 때, DP에 값이 들어있는지 여부를 따져서,

 

들어있으면 재귀하지 않고 DP값 리턴하는거고

들어있지 않으면 재귀하도록 코드를 짠다. 

그니까 방문처리를 알아서 해왔다는 소리다.

 

DP에 값이 들어있음 = 해당 재귀는 이미 끝까지 끝내놔서 값을 얻어놓은 상태.

 

이 문제의 경우, DP 값 초기화를 0으로 해서 DP에 값이 들어있는지 여부를 0으로 체크하게 된다면 

MAP 중 0이 있으면 무한루프를 돌 수 있는 위험성이 있는 문제다.

따라서 -1로 DP값을 초기화해준뒤, 메모이제이션에 값이 들어있는지를 따지는 기존의 방문처리를 DP의 값이 '-1'인지로 확인하고,
확인이 된 후에 다시 0으로 초기화해서 계산에 문제가 없도록 해주면 된다.

 

말이 복잡해서 그렇지, 그냥 메모제이션으로 구현하다보면 무슨 말인지 이해가 될 것이다!

 

#include <iostream>

using namespace std;

int N;
int MAP[100][100];
long long DP[100][100];

int mx[2] = {0, 1};
int my[2] = {1, 0};


long long dfs(int x, int y) {
    
    
    if(x == N - 1 && y == N - 1) {
        DP[N - 1][N - 1] = 1;
        return 1;
    }
    else if(DP[x][y] == -1) { // -1은 방문되지 않음을 뜻함.
        
        DP[x][y] = 0; // 방문 시 0으로 초기화하며, 값을 정상적으로 계산 가능.
        
        for(int i = 0; i < 2; i++) {
            
            int tx = x + mx[i] * MAP[x][y];
            int ty = y + my[i] * MAP[x][y];
            
            if(tx >= N || ty >= N)
                continue;
            
            DP[x][y] += dfs(tx, ty);
                        
        }
        
    }
    
    return DP[x][y];
}


int main() {
    
    cin >> N;
    
    for(int i = 0; i < N; i++) {
        
        for(int j = 0; j < N; j++) {
            cin >> MAP[i][j];
            DP[i][j] = -1;
        }
    }
    
    cout << dfs(0, 0) << "\n";
    
}

 

 

 

타뷸레이션

#include <iostream>
#define MAX(a, b) ((a >= b)? a: b)

using namespace std;


// 오른쪽, 아래로만 이동하는 것을 이용할 수 있는 풀이


int N;

int MAP[100][100];

bool CAN[100][100]; // 시작점에서 닿을 수 있는지를 체크.
long long DP[100][100]; // DP값.

int mx[2] = {0, 1};
int my[2] = {1, 0};


int main() {
    
    cin >> N;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            
            cin >> MAP[i][j];
        }
    }
    
    
    CAN[0][0] = true;
    DP[0][0] = 1;
    
    for(int i = 0; i < N; i++) {
        
        for(int j = 0; j < N; j++) {
            
            if(i == N - 1 && j == N - 1) // 도착하면 끝.
                break;
            
            if(CAN[i][j]) {
                
                for(int k = 0; k < 2; k++) {
                    
                    int tx = i + mx[k] * MAP[i][j];
                    int ty = j + my[k] * MAP[i][j];
                    
                    if(tx >= N || ty >= N)
                        continue;
                    
                                    
                    CAN[tx][ty] = true;
                    
                    DP[tx][ty] += DP[i][j];
                    
                }
            }
            
        }
    }
    
    
    cout << DP[N - 1][N - 1] << "\n";
}

 

 

 

소요 시간 : 2시간