[LeetCode] 403. Frog Jump (해석, Java 풀이)

문제

https://leetcode.com/problems/frog-jump/description/

개구리는 강을 건넌다. 강은 몇개의 unit으로 나뉘어져있고, 그곳에는 돌이 있을 수도 있고 없을수도 있다. 개구리는 돌 위에서 점프할 수 있으며 물로 뛰어들어선 안된다.

오름차순으로 정렬된 stones(돌)의 위치 리스트가 주어졌을 때, 개구리가 마지막 돌에 착륙하며 강을 건널 수 있는지 판별하라. 처음 개구리는 첫번째 돌 위에 서 있으며, 첫번째 점프는 1 unit만큼이다.

만약 개구리의 마지막 jump가 k unit만큼이었다면, 다음 점프는 k-1, k 또는 k+1 unit만큼이어야 한다. 개구리는 오직 앞으로만 갈 수 있다.

풀이

public class LeetCode_403_FrogJump {

    HashMap<Integer, Integer> m = new HashMap<>();

    boolean[][] canGo;
    boolean[][] visited;

    public boolean canCross(int[] stones) {
        if(stones[1] - stones[0] > 1) return false;
        for (int i = 0; i < stones.length; i++) {
            m.put(stones[i], i);
        }
        dp = new boolean[stones.length][stones.length];
        visited = new boolean[stones.length][stones.length];
        return dp(1, 1, stones);
    }

    private boolean dp(int stone, int jump, int[] stones) {
        if (stone == stones.length - 1) return true;       // 끝까지 왔다면 True
        if (visited[stone][jump]) return canGo[stone][jump];   // 들린적이 있다면, 해당 값 그대로 사용

        boolean canJump = false;
        for(int j : new int[]{jump - 1, jump, jump + 1}) {
            if(j > 0 && m.containsKey(stones[stone] + j)) {
                canJump = (canJump || dp(m.get(stones[stone] + j), j, stones));
            }
        }

        visited[stone][jump] = true;
        canGo[stone][jump] = canJump;

        return canGo[stone][jump];
    }
}

m: 돌이 있는 위치를 쉽게 인덱싱 할 수 있도록 만든 맵

canGo[i][j]: i 번째 돌에서 j 만큼 점프했을 때, 끝까지 도달할 수 있는지

visited[i][j]: i 번째 돌에서 j 만큼 점프했을 때를 계산한 적이 있는지

 

점프 할 수 있는 거리( jump - 1, jump, jump + 1)에 stone이 있는지 확인하고(containsKey), 

만약 있다면, 그곳으로 전진한다. 

계속해서 전진을 했을 때, 최종적으로 stones.length - 1 에 도달한다면,

마지막 돌의 위치까지 도달하여 강을 건넌것으로 true로 표시한다.

 

시간 복잡도: O(n^2), 공간 복잡도: O(n^2)

https://github.com/jeongum/java-algorithm/blob/master/dynamic_programming/LeetCode_403_FrogJump.java