[Leetcode] Jump Game IV

Insuition

Problem link: https://leetcode.com/problems/jump-game-iv/

• After assessing the problem, I believe that applying the BFS algorithm would be an effective solution.
• One of the key advantages of this approach is that it allows for multiple paths to be created from each index.
• For example, if we start at index i, we can traverse to i-1, i+1, or any other index j that has the same value as arr[i].

My Approach

• Before entering the BFS algorithm, we need to create a dictionary that includes information about the index array, which represents the same value. Then, we need to create a queue for performing BFS, which will store the index and count information.
  
  
• The key algorithm for this problem is to optimize the search process for the index array. If we have already searched for an index related to a specific value, there is no need to search for that index again. Therefore, we can clear the dictionary related to that specific value. See the code below for an example."

from collections import defaultdict, deque
from heapq import heapify, heappop, heappush
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # 1 2 3 7 1 2 2 4 7
        # 1 -> 5 -> 4 -> 9
        # cnt 작은거, 인덱스 큰것 부터 탐색

        arr_dict = defaultdict(list)

        for i in range(len(arr)):
            arr_dict[arr[i]].append(i)

        dq = deque([])

        dq.append((0, 0))
        visited = [0] * len(arr)

        while len(dq):
            f_index, f_cnt = dq.popleft()

            if f_index == len(arr) - 1:
                return f_cnt

            for i in arr_dict[arr[f_index]]:
                if not visited[i]:
                    visited[i] = True
                    dq.append((i, f_cnt + 1))

            arr_dict[arr[f_index]] = []

            if f_index - 1 >= 0 and not visited[f_index - 1]:
                visited[f_index - 1] = True
                dq.append((f_index-1, f_cnt + 1))

            if f_index + 1 < len(arr):
                visited[f_index + 1] = True
                dq.append((f_index+1, f_cnt + 1))

Other Solution