2023.03.05 Today's Challenge

fabichoi 2023. 3. 5. 23:45

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

Jump Game IV - LeetCode

Can you solve this real interview question? Jump Game IV - Given an array of integers arr, you are initially positioned at the first index of the array. In one step you can jump from index i to index: * i + 1 where: i + 1 < arr.length. * i - 1 where: i

leetcode.com

BFS로 풀면 되는 문제. 어렵. ㅠ_ㅠ

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n <= 1:
            return 0

        graph = {}
        for i in range(n):
            if arr[i] in graph:
                graph[arr[i]].append(i)
            else:
                graph[arr[i]] = [i]
        
        curs = [0]
        visited = {0}
        step = 0

        while curs:
            nex = []

            for node in curs:
                if node == n-1:
                    return step
                
                for child in graph[arr[node]]:
                    if child not in visited:
                        visited.add(child)
                        nex.append(child)

                graph[arr[node]].clear()

                for child in [node-1, node+1]:
                    if 0 <= child < len(arr) and child not in visited:
                        visited.add(child)
                        nex.append(child)

            curs = nex
            step += 1
        
        return -1