[동적 계획법, 그래프] JUMPGAME 외발 뛰기

#include <iostream>
#include <cstring>
 
#define UNTRAVELED -1
#define NO 0
#define YES 1
 
int cache[100][100];
int board[100][100];
int dy[2]{1,0};
int dx[2]{0,1};
 
bool inRange(int y, int x, int n)
{
    return ((y < n) && (x < n));
}
 
int jump(int y, int x, int n)
{
    int &ret{cache[y][x]}, nexty{}, nextx{};
    
    if(board[y][x] == 0) return YES;
    if(ret != UNTRAVELED) return ret;
    
    ret = NO;
    for(int i{0}; i < 2; i++)
    {
        nexty = y + dy[i] * board[y][x]; nextx = x + dx[i]*board[y][x];
        if(inRange(nexty,nextx,n) && !ret)
            ret = jump(nexty, nextx, n);
    }
 
    return ret;
}
 
int main(void)
{
    int testCase = 0, n = 0;
    std::cin>>testCase;
    
    for(int i{0}; i < testCase; i++)
    {
        std::cin>>n;
        memset(cache, -1, sizeof cache);
        for(int j{0}; j < n; j++)
        {
            for(int k {0}; k < n; k++)
            {
                std::cin>>board[j][k];
            }            
        }
        if(jump(0, 0, n) == YES)
            std::cout<<"YES"<<std::endl;
        else
            std::cout<<"NO"<<std::endl;
    }
}

1. 동적 게획법 메모이제이션

    다음 좌표로부터 답을 도출할 수 있는지를 기록하는 cache 배열을 만들었다.

    책에서는 반복문이 아니라 비교문을 리턴하여 답을 도출했다.

    return ret = (jump(아래쪽) || jump(오른쪽);

 

2. 기저사례

    끝지점인 board[n-1][n-1]에 도착했을 때

    한번 방문했던 좌표일때

    (책에서는 배열 범위에 벗어났을 때)

 

3. 다른 해법

    그래프로 모델링하면 간단한 문제가 된다.

 

- 알고리즘 문제해결전략 218p

JUMPGAME