[python3] 1345. Jump Game IV

풀이 일자: 23.03.05

난이도: [Hard]

분류: [Hash table, BFS]

문제 내용

arr이라는 배열이 주어졌을 때 다음과 같은 규칙으로 움직여서 배열의 끝까지 갈 때 가장 적은 step을 구하는 문제

1. 현재 위치 기준 앞뒤로 이동 가능하다. ( index범위 내에서)

2. 같은 배열값을 가지고 있는 다른 인덱스 위치로 이동 가능하다.

 

 

 

문제 해결 흐름

1. 어떤 알고리즘이 해당 문제에 적합할지 생각해보자.

→ 가장 단거리의 길을 찾는 것이 목표이므로 이를 위해 사용하는 알고리즘은 대충 DP와 그래프 순회정도이다.

 

2. DP의 경우 항상 최후의 수단으로 생각하고 일단 그래프 순회로 풀어보자.

→ DP의 경우 우선 점화식을 찾아야 하고 여러 가지를 고려해야하기에 다른 사용가능한 알고리즘을 먼저 적용해보고 안되면 DP를 고려해보는 것이 좋은 것 같다.   (적용해보는 순서: 다른 알고리즘 →  DP → 구현)

 

3. 단거리를 찾는 것이므로 그래프 순회 중에서는 BFS가 맞겠다.

→ 배열 내의 인덱스를 노드로 잡고 각 노드간의 간선(edge)는 같은 배열값을 가질 경우 해당 인덱스로 넘어갈 수 있으니까 이를 간선으로 보는 것이 적합하겠다.

 

4. 좀더 생각해본다면 arr에 같은 수가 여러 번 등장한다면 edge를 찾을 때마다 전체 탐색을 해야한다는 문제가 발생한다.

→ 일단 arr를 한번 읽어서 jump가능한 간선에 대한 정보를 dictionary로 저장하는 것이 좋겠다.

 

#TLE 발생

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        pos = dict();

        for i in range(len(arr)):
            if arr[i] not in pos:
                pos[arr[i]] = list();
            pos[arr[i]].append(i);
        
        q = deque();
        q.appendleft([0, 0]);   # index, depth

        while (1):
            i, depth = q.pop();

            if i == len(arr) - 1:
                return depth;

            if i + 1 < len(arr):
                q.appendleft([i + 1, depth + 1]);
            
            if pos[arr[i]][-1] != i:
                for j in pos[arr[i]]:
                    if j > i:
                        q.appendleft([j, depth + 1]);

            if i - 1 > 0:
                q.appendleft([i - 1, depth + 1]);

=> 일반적인 BFS를 사용했지만 시간초과가 뜨게 되었다.

 

 

 

다른 해결 방식(Official Solution)

1. 이미 방문한 곳에 대한 정보를 저장해둔다면 중복으로 계산할 필요가 없을 것이다.

→ visited라는 set을 선언하여 탐색한다.

 

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr);

        if n <= 1:
            return 0;

        graph = dict();

        for i in range(n):                       # 빠른 탐색을 위한 정리
            if arr[i] not in graph:
                graph[arr[i]] = list();
            graph[arr[i]].append(i);
        
        curs = [0];                   
        visited = set();                         # 방문한 노드
        step = 0;                                # depth

        while (curs):
            nex = [];                             # 다음 step에 방문할 노드들

            for node in curs:                     # curs 내부에 있는 노드
                if node == n-1:                   # 노드의 인덱스가 마지막이면 현재 step 리턴
                    return step;

                for child in graph[arr[node]]:    #해당 node에 있는 child모두 뽑아서
                    if child not in visited:      # 방문한 노드가 아니라면
                        visited.add(child);       
                        nex.append(child);    
                
                graph[arr[node]].clear();          # 방문한 node의 edge를 지워

                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;

=> 같은 BFS 방식이지만 동시에 처리할 수 있는 부분은 같이 처리하고 필요없는 것은 지워버려 시간을 줄인 것을 확인할 수 있다.

Time Complexity: O(N)

최악의 경우 모든 노드를 순회해야하기 때문에 arr의 길이가 시간 복잡도가 될 것이다.

 

Space Complexity: O(N)

최악의 경우 모든 노드를 visited에 저장될 것이기 때문에 arr의 길이가 공간 복잡도가 될 것이다.

2. 처음부터 하나씩 찾아나가면 너무 느리다. 앞뒤 양쪽에서 탐색을 하자.

→ 앞뒤 양쪽에서 시작해서 이들중 작은 노드를 가진 부분을 선택해서 탐색을 하다보면 중간에서 만나는 것을 이용.

 

class Solution:
    def minJumps(self, arr) -> 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 = set([0])  
        other = set([n-1])     # 앞뒤 시작점 
        
        visited = {0, n-1}
        step = 0

        while curs:
            if len(curs) > len(other):      # 현재 탐색해야 하는 두 시작점중 노드가 적은 쪽을 탐색하기 위해 교환
                curs, other = other, curs
            nex = set()

            for node in curs:
                for child in graph[arr[node]]:
                    if child in other:      # 만약에 뒤의 step에 child가 존재한 경우 끝.
                        return step + 1
                    if child not in visited:
                        visited.add(child)
                        nex.add(child)

                graph[arr[node]].clear()

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

            curs = nex
            step += 1

        return -1

Time Complexity: O(N)

최악의 경우 모든 노드를 순회해야하기 때문에 arr의 길이가 시간 복잡도가 될 것이나 이전의 방법보다는 확실히 빠를 것이다.

 

Space Complexity: O(N)

최악의 경우 모든 노드를 visited에 저장될 것이기 때문에 arr의 길이가 공간 복잡도가 될 것이다.

 

 

 

문제 링크

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

Jump Game IV - LeetCode