[LeetCode] 1345. Jump Game IV

- Problem

1345. Jump Game IV

- 내 풀이 (BFS)

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        def bfs() -> int:
            q = deque([(0, 0)])
            
            while q:
                cur, jumps = q.popleft()

                if cur == N - 1:
                    return jumps

                for nei in (cur - 1, cur + 1):
                    if 0 <= nei < N and nei not in visited:
                        visited.add(nei)
                        q.append((nei, jumps + 1))
                
                for nei in graph[arr[cur]]:
                    if nei not in visited:
                        visited.add(nei)
                        q.append((nei, jumps + 1))
                
                graph.pop(arr[cur])

        graph = defaultdict(list)
        visited = set()
        N = len(arr)

        for i, v in enumerate(arr):
            graph[v].append(i)

        return bfs()

- 결과