LeetCode - 점프 게임 III

문제 설명

음수가 아닌 정수 배열 arr이 주어지면 초기에 배열의 시작 인덱스에 위치합니다. 인덱스 i에 있을 때 i + arr[i] 또는 i - arr[i]로 점프하여 값이 0인 인덱스에 도달할 수 있는지 확인합니다.

언제든지 어레이 외부로 이동할 수 없습니다.

문제 진술 출처: https://leetcode.com/problems/jump-game-iii/

예 1:

Input: arr = [4, 2, 3, 0, 3, 1, 2], start = 5
Output: true
Explanation:
All possible ways to reach at index 3 with value 0 are:
index 5 -> index 4 -> index 1 -> index 3
index 5 -> index 6 -> index 4 -> index 1 -> index 3

예 2:

Input: arr = [4, 2, 3, 0, 3, 1, 2], start = 0
Output: true
Explanation:
One possible way to reach at index 3 with value 0 is:
index 0 -> index 4 -> index 1 -> index 3

예 3:

Input: arr = [3, 0, 2, 1, 2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

제약:

- 1 <= arr.length <= 5 * 10^4
- 0 <= arr[i] < arr.length
- 0 <= start < arr.length

설명

문제는 Jump Game 및 Jump Game II 의 확장 버전입니다. BFS 또는 DFS 접근 방식을 사용하여 이 문제를 해결할 수 있습니다.

이번 포스트에서는 BFS 방식에 대해 알아보겠습니다.

BFS 방식

우리는 시작 위치를 대기열로 밀어 넣고 이웃 탐색을 시작합니다. 방문한 노드를 표시하기 위해 부울 배열을 유지 관리해야 합니다.

먼저 알고리즘을 확인합시다.

// canReach(arr, start)

- set n = arr.size()
      queue q = [start]
      int visited[n]
      int node

- loop while !q.empty()
    node = q.start()
    q.pop()

    if arr[node] == 0
      return true

    if visited[node]
      continue

    if node - arr[node] >= 0
      q.push(node - arr[node])

    if node + arr[node] < 4
      q.push(node + arr[node])

    visited[node] = true
- while end

- return false

위 접근법의 시간복잡도는 O(N)이고 공간복잡도는
에).

C++, Golang 및 Javascript에서 솔루션을 확인합시다.

C++ 솔루션

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();
        queue<int> q{{start}};
        int node;
        vector<bool> visited(n);

        while(!q.empty()) {
            node = q.front();
            q.pop();

            if(arr[node] == 0) {
                return true;
            }

            if(visited[node]) {
                continue;
            }

            if(node - arr[node] >= 0) {
                q.push(node - arr[node]);
            }

            if(node + arr[node] < n) {
                q.push(node + arr[node]);
            }

            visited[node] = true;
        }

        return false;
    }
};

골랑 솔루션

func canReach(arr []int, start int) bool {
    n := len(arr)
    queue := []int{start}
    visited := make([]bool, n)

    for len(queue) != 0 {
        node := queue[0]
        queue = queue[1:]

        if arr[node] == 0 {
            return true
        }

        if visited[node] {
            continue
        }

        if node - arr[node] >= 0 {
            queue = append(queue, node - arr[node])
        }

        if node + arr[node] < n {
            queue = append(queue, node + arr[node])
        }

        visited[node] = true
    }

    return false
}

자바스크립트 솔루션

var canReach = function(arr, start) {
    let n = arr.length;
    let queue = [start];
    let visited = [];
    let node;

    while(queue.length > 0) {
        node = queue[0];
        queue.shift();

        if(arr[node] == 0) {
            return true;
        }

        if(visited[node]) {
            continue;
        }

        if(node - arr[node] >= 0) {
            queue.push(node - arr[node]);
        }

        if(node + arr[node] < n) {
            queue.push(node + arr[node]);
        }

        visited[node] = true;
    }

    return false;
};

주어진 입력에 대해 알고리즘을 연습해 봅시다.

Input: arr = [4, 2, 3, 0, 3, 1, 2]
       start = 5

Step 1: n = arr.size()
          = 7

        queue<int> q{{start}}
        q = [5]

        int node
        vector<bool> visited(n)

Step 2: loop while !q.empty()
        q = [5]
        true

        node = q.front()
             = 5

        q.pop()
        q = []

        if arr[node] == 0
           arr[5] == 0
           1 == 0
           false

        if visited[node]
           visited[5]
           false

        if node - arr[node] >= 0
           5 - arr[5] >= 0
           5 - 1 >= 0
           4 >= 0
           true

           q.push(node - arr[node])
           q.push(4)

           q = [4]

        if node + arr[node] < n
           5 + arr[5] < 7
           5 + 1 < 7
           6 < 7
           true

           q.push(node + arr[node])
           q.push(6)

           q = [4, 6]

        visited[node] = true
        visited[5] = true

Step 3: loop while !q.empty()
        q = [4, 6]
        true

        node = q.front()
             = 4

        q.pop()
        q = [6]

        if arr[node] == 0
           arr[4] == 0
           3 == 0
           false

        if visited[node]
           visited[4]
           false

        if node - arr[node] >= 0
           4 - arr[4] >= 0
           4 - 3 >= 0
           1 >= 0
           true

           q.push(node - arr[node])
           q.push(1)

           q = [6, 1]

        if node + arr[node] < n
           4 + arr[4] < 7
           4 + 3 < 7
           7 < 7
           false

        visited[node] = true
        visited[4] = true

Step 4: loop while !q.empty()
        q = [6, 1]
        true

        node = q.front()
             = 6

        q.pop()
        q = [1]

        if arr[node] == 0
           arr[6] == 0
           2 == 0
           false

        if visited[node]
           visited[6]
           false

        if node - arr[node] >= 0
           6 - arr[6] >= 0
           6 - 2 >= 0
           4 >= 0
           true

           q.push(node - arr[node])
           q.push(4)

           q = [1, 4]

        if node + arr[node] < n
           6 + arr[6] < 7
           6 + 2 < 7
           8 < 7
           false

        visited[node] = true
        visited[6] = true

Step 5: loop while !q.empty()
        q = [1, 4]
        true

        node = q.front()
             = 1

        q.pop()
        q = [4]

        if arr[node] == 0
           arr[1] == 0
           2 == 0
           false

        if visited[node]
           visited[1]
           false

        if node - arr[node] >= 0
           1 - arr[1] >= 0
           1 - 2 >= 0
           -1 >= 0
           false

        if node + arr[node] < n
           1 + arr[1] < 7
           1 + 2 < 7
           3 < 7
           true

           q.push(node + arr[node])
           q.push(3)

           q = [4, 3]

        visited[node] = true
        visited[1] = true

Step 6: loop while !q.empty()
        q = [4, 3]
        true

        node = q.front()
             = 4

        q.pop()
        q = [3]

        if arr[node] == 0
           arr[4] == 0
           0 == 0
           true

           return true

We return the answer as true.