JUMPGAME(C언어)

JUMPGAME

그냥 풀면 시간초과가 발생하기 때문에, DP로 접근해서 문제를 풀어야했다.

계속 문제에서 틀렸던 부분이 있었는데

원래 아래 처럼 작성했을 때에는 계속 오답이 발생했다.

*ret = jump(cache,map, x + move, y, n) + jump(cache,map, x, y + move, n);

하지만 아래처럼 바꿀경우 정답이 통과되었는데... 그 이유를 모르겠다.

*ret = jump(cache,map, x + move, y, n) || jump(cache,map, x, y + move, n);

원인해결

<정답 코드 - C언어>

#include<stdio.h>
void init_cache(int(*cache)[101]);
int jump(int (*cache)[101],int(*map)[101], int x, int y, int n);
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc, t;
    int n, i, j;
    int map[101][101];
    int cache[101][101];
    scanf("%d", &tc);
    for (t = 1; t <= tc; t++) {
 
        init_cache(cache);
 
        scanf(" %d", &n);
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                scanf(" %d", &map[i][j]);
            }
        }
 
 
        if (jump(cache, map, 0, 0, n)>0)
            printf("YES\n");
        else
            printf("NO\n");
    }
 
    return 0;
}
 
void init_cache(int(*cache)[101])
{
    int i, j;
    for (i = 0; i < 101; i++) {
        for (j = 0; j < 101; j++) {
            cache[i][j] = -1;
        }
    }
}
int jump(int(*cache)[101], int(*map)[101], int x, int y, int n)
{
 
    if (x < 0 || y < 0 || x >= n || y >= n)
        return 0;

    int move = map[x][y];
    int *ret = &(cache[x][y]);
 
    if (x == n - 1 && y == n - 1)
        return 1;
 
    if (*ret != -1)
        return *ret;
 
    *ret = 0;
 
    *ret = jump(cache,map, x + move, y, n) || jump(cache,map, x, y + move, n);
 
    return *ret;
}