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();
}
}
댓글 없음:
댓글 쓰기