Leetcode Java Frog Jump

문제

Link

코드

class Solution {

  public boolean canCross(int[] stones) {
    if (stones[1] != 1) {
      return false;
    }
    int length = stones.length;
    return this.bfs(stones, new boolean[length][length], length, 0, 1);
  }

  private boolean bfs(int[] stones, boolean[][] dp, int length, int last, int current) {
    if (current == length - 1) {
      return true;
    } else if (dp[last][current]) {
      return false;
    } else {
      int lastJump = stones[current] - stones[last];
      int next = current + 1;
      while (next < length && stones[next] <= stones[current] + lastJump + 1) {
        int increment = stones[next] - stones[current] - lastJump;
        if (increment >= -1 && increment <= 1 && this.bfs(stones, dp, length, current, next)) {
          return true;
        }
        next++;
      }
      dp[last][current] = true;
      return false;
    }
  }

}

결과

Link

설명

1. 주어진 정수 배열 stones는 강 위에 돌의 위치로, 해당 돌의 위치를 이용하여 강을 건널 수 있는지 검증하는 문제이다.
   • 단, 점프는 1부터 위치에 해당하는 숫자의 위치와 해당 위치에 -1 혹은 +1 한 값으로만 이동이 가능하다.

2. stones의 두 번째 값이 1이 아닌 경우 처음부터 이동이 불가능하므로, false를 주어진 문제의 결과로 반환한다.

3. length를 stones의 길이로 저장하고, 4번에서 정의한 bfs(int[] stones, boolean[][] dp, int length, int last, int current)메서드의 결과를 주어진 문제의 결과로 반환한다.

4. BFS 방식으로 검증할 bfs(int[] stones, boolean[][] dp, int length, int last, int current) 메서드를 정의한다.
   • current와 $length - 1$이 동일한 경우 강을 건넜으므로, true를 반환한다.
   • dp[last][current]의 값이 true인 경우 이미 검증이 수행되어 강을 건너는데 실패한 값이므로, false를 반환한다.
   • 그 외의 경우 아래를 통해 dp를 초기화한다.
     • 이전 점프 거리인 lastJump에 stones의 current번째 값과 last번째 값의 차이를 넣어준다.
     • 다음 위치 값인 next에 $current + 1$을 넣어준다.
     • next가 length 미만이고, 다음 돌의 위치인 stones[next]가 최대 점프 가능한 위치인 $stones[current] + lastJump + 1$인 경우까지 반복을 계속 수행한다.
   • 다음 점프의 증가분인 increment에 stones의 next번째 값과 current번째 값을 뺀 거리와 lastJum를 빼서 넣어준다.
   • increment가 -1 이상 1 이하의 값이고 current와 next로 재귀 호출한 결과가 true인 경우 정상적으로 점프가 되므로, true를 반환한다.
   • next를 증가시키고 계속 반복을 수행한다. - 반복이 완료되면 dp[last][current]에 true를 넣어주고, false를 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.