Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 개구리 강 건너기(Frog Jump) 문제

문제 소개

개구리 한 마리가 강을 건너는 상황을 생각해 봅시다. 강은 x개의 단위 구간으로 나뉘어 있으며, 각 단위 위치에는 돌이 있을 수도 있고 없을 수도 있습니다. 개구리는 돌 위에는 착지할 수 있지만 물 위에는 착지할 수 없습니다. 돌들의 위치가 오름차순으로 정렬된 배열로 주어졌을 때, 개구리가 마지막 돌에 착지하여 강을 건널 수 있는지 판별해야 합니다. 처음에 개구리는 첫 번째 돌 위에 서 있으며, 첫 번째 점프는 반드시 1단위여야 한다는 조건이 주어집니다.

점프 규칙

개구리의 직전 점프 거리가 k단위였다면, 다음 점프 거리는 k - 1, k, k + 1 중 하나여야 합니다. 또한 개구리는 앞쪽 방향으로만 점프할 수 있습니다.

예시

예를 들어 주어진 배열이 [0,1,3,4,5,7,9,10,12]라고 가정해 보겠습니다. 이때 답은 true입니다. 개구리가 1단위 점프로 두 번째 돌로 이동하고, 2단위 점프로 세 번째 돌로, 다시 2단위 점프로 네 번째 돌로, 이어서 3단위 점프로 여섯 번째 돌로, 4단위 점프로 일곱 번째 돌로, 마지막에는 5단위 점프로 여덟 번째 돌에 착지할 수 있기 때문입니다.

풀이 접근 방식

이 문제는 재귀 호출에 메모이제이션(결과 캐싱)을 결합하면 효율적으로 해결할 수 있습니다. 풀이 과정은 다음과 같습니다.

  • 방문 여부를 저장할 맵 visited를 정의합니다.
  • canCross() 함수를 정의합니다. 이 함수는 stones 배열과 함께, 0으로 초기화되는 현재 위치 pos와 0으로 초기화되는 직전 점프 거리 k를 매개변수로 받습니다.
  • key := pos OR (k를 11비트 왼쪽 시프트한 값)으로 고유 키를 생성합니다.
  • key가 visited에 이미 존재하면 visited[key]를 그대로 반환합니다.
  • i를 pos + 1부터 stones의 크기 미만까지 1씩 증가시키며 반복합니다.
    • gap := stones[i] - stones[pos]로 현재 위치와의 간격을 계산합니다.
    • gap이 k - 1보다 작으면 해당 지점을 건너뛰고 다음 반복으로 넘어갑니다.
    • gap이 k + 1보다 크면 더 이상 진행할 수 없으므로 visited[key] := false로 저장하고 false를 반환합니다.
    • canCross(stones, i, gap)의 호출 결과가 참이면 visited[key] = true로 저장하고 true를 반환합니다.
  • 모든 반복이 끝나면 pos가 마지막 돌의 인덱스(stones 크기 - 1)와 같을 때 visited[key] = true, 그렇지 않으면 false로 저장합니다.
  • visited[key]를 반환합니다.

구현 예제

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   unordered_map < lli, int > visited;
   bool canCross(vector<int>& stones, int pos = 0, int k = 0) {
      lli key = pos | k << 11;
      if(visited.find(key) != visited.end())return visited[key];
      for(int i = pos + 1; i < stones.size(); i++){
         int gap = stones[i] - stones[pos];
         if(gap < k - 1)continue;
         if(gap > k + 1){
            return visited[key] = false;
         }
         if(canCross(stones, i, gap))return visited[key] = true;
      }
      return visited[key] = (pos == stones.size() - 1);
   }
};
main(){
   Solution ob;
   vector<int> v = {0,1,3,5,6,8,12,17};
   cout << (ob.canCross(v));
}

이 코드의 핵심은 key를 만드는 방식입니다. 현재 위치 pos와 점프 거리 k를 하나의 정수로 압축(pos | k << 11)하여 방문 상태를 빠르게 조회할 수 있고, 이미 계산한 상태를 visited 맵에 저장하는 메모이제이션을 통해 중복 연산을 제거함으로써 시간 복잡도를 크게 줄일 수 있습니다.

입력

0,1,3,5,6,8,12,17

출력

1