JUMPGAME_알고리즘

1. 무식하게 풀기

생각

1단계. 문제는 (0, 0)에서 시작하여 (n-1, n-1) 까지 도달할 수 있는가 이다. 함수 jump를 정의 한다.

2단계. jump(y, x) 는 (y, x)좌표에서 시작해 끝까지 갈 수 있는지 반환하는 함수다.

3단계. (y, x)를 입력받은 함수는 오른쪽으로 가는 루트와 아래로가는 루트가 존재한다.

이를 점화식으로 나타내면 아래와같다.

- jump(y + m, x) || jump(y, x + m) m = 각 보드판의 숫자

코드 

// JUMPGAME_1
#include <iostream>
const int MAX = 101;
int g_JumpArray[MAX][MAX];
int g_BoardSize = 0;
 
// y, x의 좌표에서 끝까지 갈 수있는지를 반환하는 함수
int jump(int y, int x)
{
    // 기저사례1. y 또는 x 가 범위를 벗어났을때
    if (y >= g_BoardSize || y < 0) return 0;
    if (x >= g_BoardSize || x < 0) return 0;
    
    // 기저사례2. y와 x가 끝에 다달았을 때
    if (y == g_BoardSize - 1 && x == g_BoardSize - 1) return 1;
    
    // 여기에서 답을 계산한다.
    int value = g_JumpArray[y][x];
    // 점화식 : 갈수 있는 법 = (y + v, x) || (y, x + v)
    return (jump(y + value, x) || jump(y, x + value));
}
int main()
{
    // 테스트 케이스
    int testCase = 0;
    scanf("%d", &testCase);
    
    while(testCase--){
        // 보드판 크기 N * N
        scanf("%d", &g_BoardSize);
        
        // 보드판 입력
        for(int y = 0; y < g_BoardSize; y++)
        {
            for(int x = 0; x < g_BoardSize; x++)
            {
                scanf("%d", &g_JumpArray[y][x]);
            }
        }
        // 끝까지 도달 가능하다면 YES
        if(jump(0, 0))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

 

결과

2
7
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 2
1 1 1 1 1 2 0
NO
5
1 1 1 1 1 
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 0
YES

결과는 나왔지만 다음과 같은 경우에 완전탐색알고리즘은 매우 오랜시간이 걸린다.

S  1  1  1  1  1

1  1  1  1  1  1

1  1  1  1  1  1

1  1  1  1  1  1

1  1  1  1  1  2

1  1  1  1  2  E

완전 탐색의 경우 모든 경로를 탐색한 후에서야 끝으로 갈 수 없다는 것을 알 것이다.

이 과정에서 같은 경로를 몇번이나 다시 탐색할 것이고 그로인해 속도저하의 결과를 가져올 것이다.

2. 메모이제이션 적용하기(기록하기)

생각

1단계. 위의 방법에서 구현했던 함수는 입력이 (y, x)로 정해져있으면 거기서 끝까지 갈 수 있는지 없는지 는 항상 일정한참조적 투명한 함수 이다. 때문에 메모이제이션을 적용하면 같은 루트를 두번이상 계산하지 않아 속도를 향상 시킬 수 있다.

코드

// JUMPGAME_2
#include <iostream>
const int MAX = 101;
int g_JumpArray[MAX][MAX];
int g_Cache[MAX][MAX];
int g_BoardSize = 0;
 
// y, x의 좌표에서 끝까지 갈 수있는지를 반환하는 함수
int jump(int y, int x)
{
    // 기저사례1. y 또는 x 가 범위를 벗어났을때
    if (y >= g_BoardSize || y < 0) return 0;
    if (x >= g_BoardSize || x < 0) return 0;
    
    // 기저사례2. y와 x가 끝에 다달았을 때
    if (y == g_BoardSize - 1 && x == g_BoardSize - 1) return 1;
    
    // 캐시가 -1이 아니라면 캐시에 저장된 값 리턴
    int& ret = g_Cache[y][x];
    if (ret != -1) return ret;
    
    // 여기에서 답을 계산한다.
    int value = g_JumpArray[y][x];
    
    // 점화식 : 갈수 있는 법 = (y + v, x) || (y, x + v)
    ret = (jump(y + value, x) || jump(y, x + value)); //점화식
    return ret;
}
 
int main()
{
    // 테스트 케이스
    int testCase = 0;
    scanf("%d", &testCase);
    
    while(testCase--){
        // 보드판 크기 N * N
        scanf("%d", &g_BoardSize);
        
        // 보드판 입력
        for(int y = 0; y < g_BoardSize; y++)
        {
            for(int x = 0; x < g_BoardSize; x++)
            {
                scanf("%d", &g_JumpArray[y][x]);
            }
        }
        // 캐시 배열 초기화
        memset(g_Cache, -1, sizeof(g_Cache));
        
        // 끝까지 도달 가능하다면 YES
        if(jump(0, 0))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

 

결과

결과는 위의 것과 같다.

캐시를 사용하여 한번 계산한 루트에 대한 값을 저장하고 있다가 그부분에 대한 계산을 요구할 시 캐시값을 반환하는 형태로 수정하였다.

N이 커질수록 메모이제이션을 적용한 것과 안한 것의 속도차이가 커지는 것을 확인 할 수 있다.