HackerRank 자바 1D 배열 (2 부)

Question

는 내가 다음 역 추적 방식과 함께 온 다음과 같은 질문 HackerRank Java 1D Array

를 해결하기 위해 노력하고 있습니다.

import java.util.Scanner; 

public class Solution { 
static int arr[]; 

public static void main(String[] args) {  
    Scanner sc= new Scanner(System.in); 
    int T = sc.nextInt(); 
    for (int j= 0; j < T; j++) { 
     int n = sc.nextInt(); 
     arr = new int[n]; 
     int m = sc.nextInt(); 
     for (int k = 0; k< n; k++) { 
      arr[k]= sc.nextInt(); 
     } 
     if(canReach(0,arr.length,m)) 
      System.out.println("YES"); 
     else 
      System.out.println("NO"); 
    } 
} 
public static boolean canReach(int src,int dest,int m) 
{ 
    if(src>=(dest-1)||(src+m)>=dest) 
     return true; 
    if(isValidDest(src+1)&&canReach(src+1, dest, m)) 
     return true; 
    if(isValidDest(src-1)&&canReach(src-1, dest, m)) 
     return true; 
    if(isValidDest(src+m)&&canReach(src+m, dest, m)) 
     return true; 
    return false; 
} 
private static boolean isValidDest(int dest) { 
    if(((dest>=0&&dest<arr.length)&&(arr[dest]==0))) 
     return true; 
    return false; 
} 

}

그러나 나는 다음과 같은 테스트 케이스 0 0 1 1 1 0에 대한 스택 오버플로 오류를 얻고있다.

백 트랙킹 방식을 그대로 유지하면서이 스택 오버플로 오류를 피하는 방법에 대해 도움을 줄 수 있습니까?

Modified code (solution) 

import java.util.Scanner; 

public class Solution { 
static int arr[]; 
static boolean isDestVisited[]; 

public static void main(String[] args) {  
    Scanner sc= new Scanner(System.in); 
    int T = sc.nextInt(); 
    for (int j= 0; j < T; j++) { 
     int n = sc.nextInt(); 
     arr = new int[n]; 
     isDestVisited = new boolean[n]; 
     int m = sc.nextInt(); 
     for (int k = 0; k< n; k++) { 
      arr[k]= sc.nextInt(); 
     } 
     if(canReach(0,arr.length,m)) 
      System.out.println("YES"); 
     else 
      System.out.println("NO"); 
    } 
} 
public static boolean canReach(int src,int dest,int m) 
{ 
    if(src>=(dest-1)||(src+m)>=dest) 
     return true; 
    if(isDestVisited[src]==true) 
     return false; 
    isDestVisited[src]=true; 
    if(isValidDest(src+1)&&canReach(src+1, dest, m)) 
     return true; 
    if(isValidDest(src-1)&&canReach(src-1, dest, m)) 
     return true; 
    if(isValidDest(src+m)&&canReach(src+m, dest, m)) 
     return true; 
    isDestVisited[src]=false; 
    return false; 
} 
private static boolean isValidDest(int dest) { 
    if(((dest>=0&&dest<arr.length)&&(arr[dest]==0))) 
     return true; 
    return false; 
} 

}

Answer 1

재귀 ALGO에서

두 번

if (src >= dest) 
    return true; 
if (thisPositionAlreadyTested[src]) 
    return false; 
thisPositionAlreadyTested[src] = true; 
if (... 

을 동일한 상태로하는 처리를 방지하도록해야하며 동일한 목적으로 콘텐츠는