깊이 우선 탐색 (DFS, Depth-First Search)

DFS 깊이우선 탐색 알고리즘을 이용하여 풀수 있는 문제이다.
하나의 위치에서 갈 수 있는 모든 가능성에 대한 조사를 하고, 다음 위치로 넘어간다. 

* 문제 이해

n 길이의 1차 배열 arr 이 주어지고, arr[0]은 무조건 0으로 시작한다.  leap은 점프할수 있는 칸수이다.

1. 뒤로 이동
 * 만약 i-1이 존재하고, 그 인덱스의 값이 0이라면 i-1로 이동할 수 있다.
2. 앞으로 이동
 * arr[i+1]이 0이라면 한 칸을 앞으로 이동할 수 있다.
 * arr[i+leap]이 0이라면 i+leap으로 이동할 수 있다.
 * 만약 n-1에 위치하거나 i+leap>=n인 경우 win 이며 그 외는 fail이다.
 즉 인덱스 i부터 i+1 ,i-1, i+leap 번째 배열의 값이 0인 곳으로만 이동하면서 배열의 마지막에 도달하거나, 배열의 길이보다 높게 뛸 수 있으면 게임에서 이기게 된다.

문제를 풀기 위해서, 현재 위치에서 이동할 수 있는 조건들을 깊이 탐색을 해야하는 과정이 필요한데 이것은 재귀호출을 이용하여 탐색할 수 있다. 
 또한 다음 위치로 넘어가기 전에 현재 위치는 탐색을 완료했다는 표시를 반드시 해야 한다.
 그렇지 않으면 현재 위치로 다시 돌아올 경우 동일하게 탐색을 또 하기 때문에 무한루프에 빠지게 된다.

public class Solution {

     public static boolean canWin(int leap, int[] game) {
        return isSolvable(leap, game, 0); //뛸 수 있는 숫자, 배열, 시작 인덱스
    }

    private static boolean isSolvable(int leap, int[] game, int i) {
        // Base Cases
        if (i >= game.length) { //현재 위치의 인덱스가 전체 배열의 길이보다 같거나 크면
            return true; //게임에서 이김
        } else if (i < 0 || game[i] == 1) { //i가 0보다 작거나, 현재 위치의 배열 값이 1이면
            return false; //게임에서 짐
        }

        game[i] = 1; // (핵심) 현재 체크(방문)한 배열 위치의 값을 1로 마킹한다.

        // 재귀호출.

        // 현 위치에서 점프하거나, 앞으로 한칸을 가거나, 뒤로 한칸 가는 모든 상황을 체크한다. 

        // 그 중 하나라도 true를 반환한다면 게임에서 이긴다.

        // 3가지 가능한 케이스가 재귀를 돌면서 그 안에서 또 각 위치에서 세가지 케이스를 확인하므로 모든 조건에 대한 탐색이 가능하게 한다.

        return isSolvable(leap, game, i + leap) ||
                isSolvable(leap, game, i + 1) ||
                isSolvable(leap, game, i - 1);
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int q = scan.nextInt();
        while (q-- > 0) {
            int n = scan.nextInt();
            int leap = scan.nextInt();
            
            int[] game = new int[n];
            for (int i = 0; i < n; i++) {
                game[i] = scan.nextInt();
            }

            System.out.println( (canWin(leap, game)) ? "YES" : "NO" );
        }
        scan.close();
    }
}