403. Frog Jump

문제

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

제한 사항

풀이

class Solution {
    public boolean canCross(int[] stones) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = stones.length; 
        // 빠른 조회를 위해 HashMap에 돌 위치 저장
        for(int i = 0 ; i< n; i++) {
            map.put(stones[i], i);        
        }
        // dp[i][j]는 j 길이의 점프로 i번째 돌에 도달할 수 있는지 여부를 나타냄
        boolean[][] dp = new boolean[n][n];
        // 기본 케이스: 첫 번째 돌에는 0 길이의 점프로 도달 가능
        dp[0][0] = true;

        // 예외 케이스: 첫 번째 점프는 반드시 1단위여야 함
        if(stones[1] != 1) return false;

        // 모든 돌에 대해 반복
        for(int i = 0 ; i < n ; i++) {
            for(int prevJump = 0 ; prevJump < n ; prevJump++) {
                // 현재 돌에 prevJump 길이로 도달할 수 있다면
                if(dp[i][prevJump]) {
                    for(int nextJump = Math.max(prevJump-1, 1) ;
                    nextJump < prevJump+2; nextJump++) {
                        int nextPosition = stones[i] + nextJump;
                        // 다음 위치에 돌이 있는지 확인
                        if(map.containsKey(nextPosition)) {
                            int nextIndex = map.get(nextPosition);
                            dp[nextIndex][nextJump] = true;
                        }
                    }
                }
            }
        }

        // 어떤 점프 길이로든 마지막 돌에 도달할 수 있는지 확인
        for(int jump = 0; jump< n ; jump++) {
            if(dp[n-1][jump] == true ) return true;
        }
        return false;
    }
}

회고

DP 문제이면서도 제한 조건의 범위가 크지 않아서 O(n^2)을 허용하는 문제였다. DP 배열을 정의하는 것이 쉽지 않았다. 그리고 최대 점프 길이 반드시 알아야 하는 문제였다. k는 1부터 시작해서 k-1, k, k+1 중 하나의 길이만큼 점프를 한다. 점프한 만큼의 값(stones[i] + nextJump)이 현재 인덱스 뒤에 존재하면 해당 인덱스로 건널 수 있다. 점프 가능한 최대 길이는 (stones의 길이-1)이다. 왜냐하면 인덱스 끝까지 k가 증가(k+1)하는 추세라도 stones의 길이까지만 증가할 수 있기 때문이다.

 

dp[i][j]는 j만큼 뛰어서 i 번째 돌에 도달 가능한지 여부를 나타낸다. dp[0][0] = true를 시작으로 각 돌 위치에서 점프 가능한 돌 위치를 판별할 수 있다. 존재 유무를 판별 가능한 이유 중 하나는 Map으로 위치 별 값을 미리 저장하고 있기 때문이다. Map으로 존재 유무를 판별하는 시간 복잡도는 O(1)이다.

 

풀이를 요약하자면,

1. 돌 위치 별 값을 미리 저장한다. Map을 이용한다.
2. dp[0][0]을 시작으로 각 돌 위치 별 점프로 도달 가능한 돌이라면, 해당 돌에서 어떤 돌로 점프 가능한지 판별한다. (k-1, k, k+1) 점프를 시도한다. 점프한 돌의 값이 Map에 존재하면 dp[nextIndex][nextJump]를 true로 업데이트한다. 왜나햐면 Map에 존재한다는 것은 점프해서 갈 수 있는 돌이 존재한다는 의미로 받아들일 수 있기 때문이다.
3. 마지막 돌에서, 점프 길이에 따라 마지막 돌에 도달 가능한지 여부를 판단한다. 그 중 하나라도 있으면 true를 반환한다.