JUMPGAME

뻔한·2020년 4월 13일
0

Dynamic programming

목록 보기
11/16

문제 링크

JUMPGAME

문제 풀이

각 칸의 값만큼 오른쪽이나 아래쪽으로 이동하여 끝 점에 도달할 수 있는지 확인하는 문제이다. 이는 완전 탐색을 통해 풀 수 있지만, 도달하는 경로가 없는데 경우의 수는 많은 경우에 문제가 된다. 완전 탐색으로 만들어지는 경로의 수는 n에 지수적으로 늘어나므로, 시간 제한에 걸리게 된다.
이 문제로 만들어지는 완전 탐색으로 만들어지는 경로는 많지만 이동할 수 있는 좌표들은 100 ×\times 100 = 10000개 뿐이므로 비둘기집의 원리에 따라 중복되는 부분 문제들이 존재한다. 그리고 출력이 입력 값만으로 결정되므로 동적계획법을 사용해서 풀 수 있다.

판을 넘어가는 경우와 끝 점에 도달한 경우를 기저 사례로 처리한다. 그리고 메모이제이션을 적용하여 해당 좌표에서 끝 점까지 도달 여부를 cache에 저장한다.

구현


#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

int Tcase;
int n;
int board[100][100];
int cache[100][100];

int Jump(int y, int x) {
    if (y >= n || x >= n ) return 0;
    if (y == n -1 && x == n-1 ) return 1;
    
    int& ret = cache[y][x];
    if (ret != -1) return ret;

    ret = Jump(y + board[y][x], x) || Jump(y, x + board[y][x]);

    return ret;
}

int main() {	
    cin >> Tcase;
    while (Tcase--) {
        cin >> n;

        memset(cache, -1, sizeof(cache));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> board[i][j];
                
        if(Jump(0, 0) == 1) cout << "YES" << endl;
        else cout << "NO" << endl;   
    }
    return 0;
}
profile
ㄷㄷㄷㅈ

0개의 댓글