JUMPGAME

문제 :https://algospot.com/judge/problem/read/JUMPGAME

배열에서 해당 위치의 값 만큼 오른쪽이나 아래쪽으로 이동하여 배열의 마지막 부분으로 이동하는 것이 가능한지 아닌지를 구하는 프로그램인데, 기존의 재귀 호출을 이용하여 (0, 0)에서 (N-1, N-1)의 위치로 탐색 하게 되면 목적지로 가지 않는 이동 경로도 탐색 하기 때문에 많은 시간을 필요로 한다.

그렇기 때문에 (N-1, N-1)에서 (0, 0)으로 반대로 탐색하게 되면 목적지로 향하는 알맞은 값을 탐색해 나가기 때문에 시간을 단축하고 원하는 결과를 얻을 수 있다.

출력 결과:

알고스팟 결과:

#include<iostream> using namespace std; bool move(int(*arr)[100], int _i, int _j, int no){ bool result = false; if (_i == 0 && _j == 0) result = true; else{ int num = 1; for (int i = _i - 1; i >= 0; i--){ if (result == true) return true; if (arr[i][_j] == num) if (move(arr, i, _j, no)) result = true; num++; } num = 1; for (int j = _j - 1; j >= 0; j--){ if (result == true) return true; if (arr[_i][j] == num) if (move(arr, _i, j, no)) result = true; num++; } } return result; } int main(void){ int testcase; cin >> testcase; int arr[100][100] = { 0, }, no; bool result; while (testcase--){ cin >> no; for (int i = 0; i < no; i++){ for (int j = 0; j < no; j++){ cin >> arr[i][j]; } } result = move(arr, no - 1, no - 1, no); if (result) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }