각 칸의 값만큼 오른쪽이나 아래쪽으로 이동하여 끝 점에 도달할 수 있는지 확인하는 문제이다. 이는 완전 탐색을 통해 풀 수 있지만, 도달하는 경로가 없는데 경우의 수는 많은 경우에 문제가 된다. 완전 탐색으로 만들어지는 경로의 수는 n에 지수적으로 늘어나므로, 시간 제한에 걸리게 된다.
이 문제로 만들어지는 완전 탐색으로 만들어지는 경로는 많지만 이동할 수 있는 좌표들은 100 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;
}