[LeetCode] 403. Frog Jump | C++

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

문제 설명

개구리가 강을 건너려고 한다. 강은 돌이 존재해서 개구리는 돌 위에만 착지하며 갈 수 있으며 물 위에는 설 수 없다.
돌의 위치가 오름차순으로 주어진다.

개구리는 처음 위치 0번(첫 돌)에서 출발하여, 첫 점프는 반드시 1칸이다.
만약 직전 점프 거리가 k 라면 다음 점프는 k-1, k, k+1 중 하나의 거리여야한다.
점프 거리는 항상 양수고 앞으로만 이동한다.

개구리가 마지막 돌에 도착할 수 있는지 판별해야한다.

예시

입력 :

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

출력:

true

설명:
개구리가 0번에서 시작해서 첫 점프는 1칸으로 1번 돌로 간다.
다음은 1칸 또는 2칸 이동 가능하다. (k, k+1 가능, k-1은 0으로 불가능)
따라서 2번 혹은 3번 돌로 가야하는데 2번돌은 없으므로 3번 돌에 착지할 수 있다.
직전 2칸 이동했으므로 다음은 1칸, 2칸, 3칸 이동 할 수 있다.
즉 4번돌, 5번돌, 6번돌 가능한데 5번돌 또는 6번돌에 착지가능하다.
[5번돌에 갔을 때] 직전 2칸 이동했으므로 다음은 1칸, 2칸, 3칸 이동할 수 있다.
즉 6번돌, 7번돌, 8번돌 가능한데 6번 또는 8번돌에 착지가능하다.
직전 3칸 이동했으므로 다음은 2, 3, 4칸 이동할 수 있다. 10, 11, 12번 돌에 착지가능하고, 12번에 갈 수 있다.
직전 4칸 이동했으므로 다음은 3,4,5칸 이동할 수 있다. 15, 16, 17번 돌 착지 가능하고, 17번 돌에 도달가능하므로 true 를 출력한다.

풀이

1. 상태 정의

예시에서 봤듯
우선 '돌이 있고 개구리는 현재 위치와 직전 점프 길이 k라는 상태를 가지고 있다'

현재 위치 (idx, k)라고 한다면 1번돌에 있고 직전 점프 길이가 1인 개구리의 상태는 (1, 1)로 둘 수 있다.
3번 돌에 있고 직전 점프 길이가 2칸인 개구리는 (3, 2)로 둘 수 있다.

2. 전이 정리

(idx, k) 인 개구리는 k-1, k, k+1 만큼 점프할 수 있으며 점프한 위치에 '돌'이 있어야 착지할 수 있다.

(idx+k, k)
(idx+k-1, k-1)
(idx+k+1, k+1)
중 착지 가능 한 위치로 전이된다.

3. 기저 조건 / 정리 조건

만약 idx=0 위치가 0인 경우는 시작 지점이므로 pass
idx=1) 위치가 1인 경우는 (1, 1)의 상태를 가지고 (2, 1) (3, 2) 중 돌이 있는 곳 전이 가능

즉 기저 조건은 이렇다.
idx=0 (0, 0) 상태로 바로 true 리턴
idx=1 (1, 1) 상태로 바로 true 리턴

정리 조건은 idx가 stones[-1]에 도달했을 때이다.

4. 어떤 자료 구조?

지금 보면 전이 상태에 따라 다음 위치에 돌이 있을지 그때 그때 빠르게 확인이 가능해야한다. 그런데 벡터 자료 구조에선 해당 과정이 비효율적이기 때문에

해시 맵으로 구현하려고 한다.

unordered_map<int, int> pos_to_idx 로 돌 위치를 키로 하고, stones 배열의 인덱스를 값으로 하는 자료구조를 만들면 된다.

pos_to_idx[16], pos_to_idx[17] 이런식으로 접근하면 바로 바로 해당하는 돌이 있는지 확인할 수 있다.

이제 핵심은 (idx, k) 상태를 기반으로 DFS + 메모이제이션으로 풀어내는 것이다.

• 상태: (idx, k)
• 전이: nk ∈ {k-1, k, k+1} (단 nk > 0)
• 다음 위치 = stones[idx] + nk
• 존재 여부: pos_to_idx로 확인 후 인덱스 추출
• 종료: idx == 마지막 돌

로 일반화가 되었으니 해당하는 상태에 대한 값이 이미 계산되어있다면 계산하지 않고 memo하는 것이 효율적이다.

코드

코드는 이렇게 작성하였다.

#include <vector>
#include <iostream>
#include <unordered_map>
#include <map>   // map 사용을 위해 추가

typedef pair<int, int> state;  // 상태 = (현재 위치, 직전 점프 길이)

using namespace std;

class Solution {
private:
    // DFS 함수: 현재 상태(st)에서 마지막 돌까지 도달 가능한지 탐색
    bool dfs(state st, vector<int>& stones, unordered_map<int, int>& pos_to_idx, map<state, bool>& dp) {
        int now_pos = st.first;  // 현재 돌의 위치
        int k = st.second;       // 직전 점프 길이

        // 마지막 돌에 도착한 경우 성공
        if (now_pos==stones.back()) return true;

        // 이미 계산된 상태라면 메모된 값 반환
        if (dp.count(st)) return dp[st];

        // 점프 길이가 0 이하라면 불가능
        if (k <= 0) return dp[st] = false;

        // 다음 점프 시도 (k-1, k, k+1)
        for (int i=-1; i<=1; i++) {
            int new_k = k + i;          // 새로운 점프 길이
            int new_pos = now_pos + new_k;  // 새로운 위치

            // 해당 위치에 돌이 없으면 건너뜀
            if (pos_to_idx.find(new_pos) == pos_to_idx.end()) continue;

            // 해당 돌로 이동 가능하다면 DFS 재귀 호출
            if (dfs(make_pair(new_pos, new_k), stones, pos_to_idx, dp)) 
                return dp[st] = true;   // 하나라도 성공하면 true 기록 및 반환
        }
        // 세 경우 모두 실패 → false 기록 및 반환
        return dp[st] = false;
    }

public:
    bool canCross(vector<int>& stones) {
        unordered_map<int, int> pos_to_idx; // 돌 위치 → 인덱스 매핑
        map<state,bool> dp;                 // 메모이제이션 (상태 → 가능 여부)

        // 시작 조건: 첫 돌은 반드시 0, 두 번째 돌은 반드시 1
        if (stones[0]!=0 || stones[1] != 1) return false;

        // 돌 위치를 pos_to_idx에 저장
        for (int i=0; i<stones.size(); i++) {
            pos_to_idx[stones[i]] = i;
        }

        // 초기 상태: 1번 위치에서 시작, 직전 점프는 1칸
        return dfs(make_pair(1, 1), stones, pos_to_idx, dp);
    }
};

LeetCode에 제출하여 시간복잡도 O(N*M) 으로 통과하였다.