Java Coding Test 타일 점프

---

문제

---

이 문제는 주어진 타일 배열에서 최소 점프 횟수를 찾는 문제입니다. 각 타일에 적힌 수는 현수가 그 타일에서 오른쪽으로 점프할 수 있는 최대 거리를 나타냅니다. 이 문제를 해결하기 위해, 현수가 각 타일에서 점프할 수 있는 최대 범위를 고려하면서 목적지에 도달할 수 있는 최소 점프 횟수를 계산해야 합니다.

다음과 같은 접근 방법을 사용할 수 있습니다:

1. 현수의 현재 위치를 나타내는 변수와 현재 위치에서 점프할 수 있는 최대 거리를 나타내는 변수를 초기화합니다.
2. 배열을 순회하면서 각 타일에서 점프할 수 있는 최대 거리를 계산합니다.
3. 현수가 점프할 수 있는 최대 거리를 갱신하면서 최소 점프 횟수를 계산합니다.
4. 만약 어느 시점에서도 상점에 도달할 수 없다면 -1을 반환합니다.

이제 이 로직을 코드로 구현해 보겠습니다.

현수가 집에서 상점까지 갈 수 있는 최소 점프 횟수는 4번입니다. 이는 입력된 타일 배열 [2, 3, 1, 1, 2, 4, 2, 0, 1, 1]에 대해 계산한 결과입니다. 이 배열은 현수가 각 타일에서 점프할 수 있는 최대 거리를 나타냅니다. 따라서 현수는 최소 4번의 점프로 상점에 도달할 수 있습니다.

---

나의 풀이

---

package inflearn_231118;

import java.util.*;
class Solution3 {
	public int solution(int[] nums){
		int answer = -1,l=0,end=nums.length;
		Queue<Integer> Q = new LinkedList<>();
		
		Q.offer(0);
		
		while(!Q.isEmpty()) {
			int len=Q.size();
			for(int i=0;i<len;i++) {
				int x=Q.poll();
				for(int j=1;j<=nums[x];j++) {
					int nx = x+j;
					if(nx==end-1)
						return l+1;
					Q.offer(nx);
				}
			}
			l++;
		}
		return answer;
	}
		
	public static void main(String[] args){
		Solution3 T = new Solution3();
		System.out.println(T.solution(new int[]{2, 2, 1, 2, 1, 1}));
		System.out.println(T.solution(new int[]{1, 0, 1, 1, 3, 1, 2, 1}));
		System.out.println(T.solution(new int[]{2, 3, 1, 0, 1, 1, 2, 3, 1, 5, 1, 3, 1}));
		System.out.println(T.solution(new int[]{1, 2, 1, 2, 1, 2, 1, 1, 3, 1, 2, 1}));
		System.out.println(T.solution(new int[]{1, 3, 2, 1, 1, 2, 3, 1, 3, 1, 2, 3, 5, 1, 5, 1, 2, 1, 1}));
	}
}

---

테스트

---

---