[LeetCode][DFS|BFS] 1654. Minimum Jumps to Reach Home

 

문제 링크

https://leetcode.com/problems/minimum-jumps-to-reach-home/

Minimum Jumps to Reach Home - LeetCode

A certain bug's home is on the x-axis at position x. Help them get there from position 0.

The bug jumps according to the following rules:

• It can jump exactly a positions forward (to the right).
• It can jump exactly b positions backward (to the left).
• It cannot jump backward twice in a row.
• It cannot jump to any forbidden positions.

The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.

Given an array of integers forbidden, where forbidden[i] means that the bug cannot jump to the position forbidden[i], and integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x, return -1.

 

Example 1:

Input: forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
Output: 3
Explanation: 3 jumps forward (0 -> 3 -> 6 -> 9) will get the bug home.

Example 2:

Input: forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
Output: -1

Example 3:

Input: forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
Output: 2
Explanation: One jump forward (0 -> 16) then one jump backward (16 -> 7) will get the bug home.

 

Constraints:

• 1 <= forbidden.length <= 1000
• 1 <= a, b, forbidden[i] <= 2000
• 0 <= x <= 2000
• All the elements in forbidden are distinct.
• Position x is not forbidden.

 

 

문제 해석

 

진짜 진짜.. 너무 짜쳤던(?) 문제다.. 

결론부터 말하면 BFS 또는 DFS로 풀면 해결되는 문제이긴 하다.

 

여기서 중요한 조건은 "It cannot jump backward twice in a row."

위 조건을 바탕으로 bug가 위치할 수 있는 최대 위치는 2000 + b * 2가 된다. 

 

또한, 위 조건에 따라 visit check를 다르게 해 주어야 한다.

forward로 왔을 수도 있고, backward로 왔을 수도 있기 때문!

 

조건을 꼼꼼하게 잘 체크해야 하는 문제.. :p

 

 

 

 

 

제출 코드

 

먼저,  BFS로 풀어 제출한 코드이다. 

이후에 언급하긴 하겠지만 아래 코드는 상당히 느리다... 

이유는 forbiddenList! 매번 contains함수를 사용해 체크해 주다보니 시간이 많이 걸린 듯 하다. 

(제출 시, 132ms 소요.. 속도는 100명 중 뒤에서 7등 ^^..)

class Solution {
    List<Integer> forbiddenList;
    List<Node> queue;
    Set<Integer> forwardVisitSet;
    Set<Integer> backwardVisitSet;
    int backward;
    
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        backward = b;
        forwardVisitSet = new HashSet<>();
        backwardVisitSet = new HashSet<>();
        forbiddenList = new ArrayList<>();
        for (int i = 0; i < forbidden.length; i++) forbiddenList.add(forbidden[i]);
        
        queue = new ArrayList<>();
        queue.add(new Node(0, 0, true));
        forwardVisitSet.add(0);
        backwardVisitSet.add(0);
        
        int result = -1;
        
        while(queue.size() > 0) {
            Node popNode = queue.remove(0);
            int pos = popNode.pos;
            
            if (pos == x) {
                result = popNode.count;
                break;
            }
            
            if (checkCondition(pos + a) && !forwardVisitSet.contains(pos + a)){
                forwardVisitSet.add(pos + a);
                queue.add(new Node(pos + a, popNode.count + 1, true));
            }
            if (checkCondition(pos - b) && !backwardVisitSet.contains(pos - b) && popNode.canBackward){
                backwardVisitSet.add(pos - b);
                queue.add(new Node(pos - b, popNode.count + 1, false));
            }
        }
        
        return result;
    }
    
    private boolean checkCondition(int pos) {
        return (pos >= 0 && pos <= 2000 + 2 * backward) && !checkForbidden(pos);
    }
    
    private boolean checkForbidden(int pos) {
        return forbiddenList.contains(pos);
    }
}

class Node {
    int pos;
    int count;
    boolean canBackward;
    
    Node(int pos, int count, boolean canBackward) {
        this.pos = pos;
        this.count = count;
        this.canBackward = canBackward;
    }
}

 

DFS와 비교해 보기 위해서 BFS → DFS로 코드를 변경한 후 조금 정리해 주었다.

정리해 주기 전에 걸린 시간은 BFS < DFS로 DFS가 더 오래 걸렸다. (+60ms정도?)

정리를 해 주니.... 14ms대로 HOOK 감소했다..!! (두둥-)

class Solution {
    Set<Integer> forwardVisitSet;
    Set<Integer> backwardVisitSet;
    int home;
    int forward;
    int backward;
    int result;
    
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        home = x;
        forward = a;
        backward = b;
        forwardVisitSet = new HashSet<>();
        backwardVisitSet = new HashSet<>();
        for (int i = 0; i < forbidden.length; i++) {
            forwardVisitSet.add(forbidden[i]);
            backwardVisitSet.add(forbidden[i]);
        }
        
        forwardVisitSet.add(0);
        backwardVisitSet.add(0);
        
        result = -1;
        func(0, 0, true);
        
        return result;
    }
    
    private void func(int pos, int count, boolean backwardFlag) {
        if (pos == home) {
            if (result == -1 || count < result) result = count;
            return;
        }
        
        if (checkRange(pos + forward) && !forwardVisitSet.contains(pos + forward)) {
            forwardVisitSet.add(pos + forward);
            func(pos + forward, count + 1, true);
        }
        if (checkRange(pos - backward) && !backwardVisitSet.contains(pos - backward) && backwardFlag) {
            backwardVisitSet.add(pos - backward);
            func(pos - backward, count + 1, false);
        }
    }
    
    private boolean checkRange(int pos) {
        return (pos >= 0 && pos <= 2000 + 2 * backward);
    }
}

 

 

 

 

제출 결과

 

두 번째 코드 제출 시 아래와 같은 결과를 확인할 수 있다.

 

 

 

참고 링크

 

 

 

 

 

 

사실 이 문제.. 제출을 생각보다 많이 해서 풀고도 뿌듯하지 않았다.. 

너무 쉽게 보았나 보당 좀더 꼼꼼할 필요가 이쒀! ㅜㅜ

- mushroong

 

 

 

 

---