알고리즘/Leetcode

[Leetcode]1306. Jump Game III

응애~ 개발자 2025. 5. 7. 19:52
728x90
반응형

문제 요약

  • 알고리즘 분류: Tree, DFS, BFS
  • 난이도: Medium
  • 문제내용:
    • 배열 arr이 주어지고, 여러분은 처음에 start 인덱스에 위치해 있습니다.
    • 인덱스 i에 있을 때, 여러분은 i + arr[i] 또는 i - arr[i]로 점프할 수 있습니다.
    • 값이 0인 인덱스에 도달할 수 있는지 true, false로 반환 하면 됩니다.
  • 사이트 주소: https://leetcode.com/problems/jump-game-iii/description/

문제풀이

 이번 문제는 방향성 그래프는 아니지만 잘보면 간단하게 그래프 탐색으로 풀수 있는 문제이다. 그레프 탐색은 대표적으로 깊이 우선 탐색(DFS), 넓이 우선 탐색(BFS)이 있다. 그래프 탐색에 대한 내용은 아래 글에서 확인 해보면 된다.

문제 이해하기

이 문제를 이해하기 위한 핵심 포인트는 다음과 같습니다:

  1. 특정 시작 인덱스에서 시작합니다.
  2. 각 인덱스에서 두 가지 방향으로 점프할 수 있습니다:
    • 앞으로: 현재 인덱스 + 현재 위치의 배열 값
    • 뒤로: 현재 인덱스 - 현재 위치의 배열 값
  3. 목표는 값이 0인 인덱스에 도달할 수 있는지 확인하는 것입니다.
  4. 배열 밖으로 나갈 수 없습니다.

접근 방법

이 문제는 그래프 탐색 문제로 생각할 수 있습니다. 각 인덱스를 노드로, 각 가능한 점프를 간선으로 생각해 볼 수 있습니다. 우리의 목표는 시작 노드에서 값이 0인 노드로 가는 경로가 있는지 확인하는 것입니다.

이런 종류의 문제는 BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)로 해결할 수 있습니다. 아래와 같이 BFS로 구현 하면됩니다.

 

  • 시작 인덱스를 큐에 넣고 방문했다고 표시합니다.
  • 큐가 비어 있지 않는 동안:
    • 큐에서 현재 인덱스를 꺼냅니다.
    • 현재 인덱스의 값이 0이면 목표에 도달했으므로 true를 반환합니다.
    • 현재 인덱스에서 가능한 두 가지 점프(앞으로, 뒤로)를 시도합니다.
    • 점프한 위치가 배열 범위 내에 있고 아직 방문하지 않았다면, 큐에 추가하고 방문했다고 표시합니다.
  • 모든 가능한 점프를 시도했지만 값이 0인 인덱스에 도달하지 못했다면 false를 반환합니다.

BFS는 위 구현에서 queue에서 stack으로 변경만 하면 됩니다.

마무리

위 처럼 구현하면 시간복잡도는 배열 길이 만큼 O(N)이 나올 것입니다.

Jump Game III 문제는 그래프 탐색의 개념을 배열 탐색에 적용하는 좋은 예입니다. BFS 또는 DFS를 사용하여 해결할 수 있으며, 두 방법 모두 효율적입니다. 문제를 그래프 탐색으로 모델링하는 능력은 알고리즘 문제 해결에 있어 매우 중요한 기술입니다.

 

Code

Python

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        size = len(arr) # 배열의 길이
        visited = [False] * size # 각 인덱스 방문 여부를 추적하기 위한 배열을 초기화

        queue = deque([start]) # BFS(너비 우선 탐색)를 위한 큐를 생성
        visited[start] = True # 시작 인덱스를 큐에 추가하고 방문했다고 표시

        # 큐가 비어있지 않는 동안 반복
        while queue:

            index = queue.popleft() # 큐에서 현재 탐색할 인덱스

            # 현재 인덱스의 값이 0이면 목표에 도달했으므로 true를 반환
            if arr[index] == 0:
                return True

            # 현재 인덱스 값 왼쪽, 오른쪽 위치 계산
            for next_index in (index - arr[index], index + arr[index]):

                # 다음 인덱스 위치가 범위 안 그리고 방문하지 않았다면
                if 0<= next_index < size and not visited[next_index]:
                    # 해당 인덱스를 큐에 추가하고 방문했다고 표시
                    queue.append(next_index)
                    visited[next_index] = True

        # 모든 가능한 점프를 시도했지만 값이 0인 인덱스에 도달하지 못했으므로 false를 반환
        return False

Java

class Solution {
    public boolean canReach(int[] arr, int start) {
        
        // 배열의 길이
        int size = arr.length;
        // 각 인덱스 방문 여부를 추적하기 위한 배열을 초기화
        boolean[] visited = new boolean[size];

        // BFS(너비 우선 탐색)를 위한 큐를 생성
        Queue<Integer> queue = new LinkedList<>();
        // 시작 인덱스를 큐에 추가하고 방문했다고 표시
        queue.add(start);
        visited[start] = true;

        // 큐가 비어있지 않는 동안 반복
        while(!queue.isEmpty()){
            // 큐에서 현재 탐색할 인덱스
            int index = queue.poll();

            // 현재 인덱스의 값이 0이면 목표에 도달했으므로 true를 반환
            if(arr[index] == 0){
                return true;
            }

            // 현재 인덱스에서 왼쪽(이전)으로 점프할 위치를 계산
            int before = index - arr[index];
            // 왼쪽 점프가 배열 범위 내에 있고 아직 방문하지 않았다면
            if(before >=0 && !visited[before]){
                // 해당 인덱스를 큐에 추가하고 방문했다고 표시
                queue.add(before);
                visited[before] = true;
            }

            // 현재 인덱스에서 오른쪽(이후)으로 점프할 위치를 계산
            int after = index + arr[index];
            // 오른쪽 점프가 배열 범위 내에 있고 아직 방문하지 않았다면
            if(after < size && visited[after] == false){
                // 해당 인덱스를 큐에 추가하고 방문했다고 표시
                queue.add(after);
                visited[after] = true;
            }
        }

        // 모든 가능한 점프를 시도했지만 값이 0인 인덱스에 도달하지 못했으므로 false를 반환
        return false;
    }
}

 

Javascript

위 코드와 다르게 자바스크립트는 DFS로 풀었다. 이유는 자바스크립트에서는 자체 큐가없어서 직접 구현해야되는 일이 생긴다. 큐를 구현 하는것보다 배열을 stack처럼 활용 할 수 있어서 DSF로 푸는것이 더 좋다고 생각한다.

var canReach = function(arr, start) {
    const size = arr.length; // 배열의 길이
    // 각 인덱스 방문 여부를 추적하기 위한 배열을 초기화
    let visited = Array(size).fill(false);

    // DFS(깊이 우선 탐색) 위한 Stack 생성
    let stack = [];
    // 시작 인덱스를 큐에 추가하고 방문했다고 표시
    stack.push(start);
    visited[start] = true;

    // 스택 비어있지 않는 동안 반복
    while(stack.length > 0) {
        // 스택에서 현재 탐색할 인덱스
        const index = stack.pop();

        // 현재 인덱스의 값이 0이면 목표에 도달했으므로 true를 반환
        if(arr[index] == 0){
            return true;
        }

        // 현재 인덱스에서 왼쪽(이전)으로 점프할 위치를 계산
        const before = index - arr[index];
        // 왼쪽 점프가 배열 범위 내에 있고 아직 방문하지 않았다면
        if(index - arr[index] >=0 && !visited[before]){
            // 해당 인덱스를 큐에 추가하고 방문했다고 표시
            stack.push(before);
            visited[before] = true;
        }

        // 현재 인덱스에서 오른쪽(이후)으로 점프할 위치를 계산
        const after = index + arr[index];
        // 오른쪽 점프가 배열 범위 내에 있고 아직 방문하지 않았다면
        if(after < size && visited[after] == false){
            // 해당 인덱스를 큐에 추가하고 방문했다고 표시
            stack.push(index + arr[index]);
            visited[after] = true;
        }
    }

    return false
};
728x90
반응형