[Leetcode(릿코드)/55] Jump Game (Medium, Java)

Question

• 문제 링크 : https://leetcode.com/problems/jump-game/

• 분류 : BFS

• 풀이 시간 : 30분

  삽질) 풀이 1 : 1 ~ nums[idx]칸씩 이동해보고 되돌아오는 백트래킹으로 풀었으나 시간초과

  정답) 풀이 2 : BFS로 1 ~ nums[idx]칸씩 이동하면서 방문 여부 체크

문제 해설

1. 음이 아닌 정수 배열 nums
2. 배열의 각 요소는 해당 위치에서 최대 점프 길이냄
3. 처음에는 배열의 첫 번째 인덱스 에 위치
4. 인덱스에서 점프하면서 배열의 끝에 도달 할 수 있는지 확인하십시오.

Solution

풀이 접근 방법

1. 이동하는 경우의 수 계산
   1. 백트래킹 : 범위가 너무 크고 중복된 위치에 도달하는 경우 많아서 시간초과 발생
      1. 1 <= nums.length <= 3 * 104
      2. 0 <= nums[i] <= 105
   2. BFS : 큐 사용하여 방문 탐색

정답 코드

class Solution {
    public int N;
    public boolean canJump(int[] nums) {
      	// 배열의 길이 
        N = nums.length;
        
        boolean[] visited = new boolean[nums.length];
        Queue<Integer> queue = new LinkedList<Integer>();
    
        visited[0] = true;
        queue.add(0);
        
        while(!queue.isEmpty()) {
            int idx = queue.poll();
            
            // 현재 배열의 위치에서 점프할 수 있는 길이만큼 다 이동해보기
            for (int i = 1; i <= nums[idx]; i++) {
                int newIdx = idx + i;
                
                // 점프했을 때 범우 밖이거나 이미 방문했었으면 탐색 X
                if (!isIn(newIdx) || visited[newIdx])
                    continue;
                
                // 배열의 끝에 도달했으면 종료
                if (newIdx == N - 1)
                    return true;
                
                visited[newIdx] = true;
                queue.add(newIdx);
            }
        }
        
        return visited[N-1];
    }
    
    public boolean isIn(int x) {
        if (0 <= x && x < N)
            return true;;
        return false;
    }
    
}