Lesson 13. Fibonacci numbers - FibFrog #3 (속도 개선)

1. 속도 개선 아이디어

아무래도 재귀함수로는 한계가 있어보인다.

너비 우선 탐색(BFS, Breadth First Search)을 이용해서 전체 탐색하도록 수정해 보자.

 

2. 코드 (C++)

BFS로 전체 탐색 구현

#include <queue>

int solution(vector<int> &A) {

    int destination = A.size() + 1;

    //generate fibonacci numbers
    vector<int> fib = {};
    fib.emplace_back(0);
    fib.emplace_back(1);
    int M = 2;
    int n = fib[1] + fib[0];
    while(n <= destination)
    {
        fib.emplace_back(n);
        M++;
        n = fib[M - 1] + fib[M - 2];
    }

    //generate leaves vector that contains only the leaves that can be jumped to
    vector<int> leaves = {};
    leaves.emplace_back(0);
    for(size_t i = 0; i < A.size(); i++)
    {
        if(A[i] == 1) leaves.emplace_back(i + 1);
    }
    leaves.emplace_back(destination);

    //Count the minimum number of jumps to the other side of a river
    queue<pair<int, int>> q = {}; // queue<current position, current jump>
    int min_jump = numeric_limits<int>::max();
    for(size_t i = 1; i < leaves.size(); i++)
    {
        auto it = find(fib.begin() + 2, fib.end(), leaves[i]);
        if(it == fib.end()) continue;

        q.push({i, 1});
        while(!q.empty())
        {
            int cur_pos = q.front().first;
            int cur_jump = q.front().second;
            q.pop();

            if(cur_jump >= min_jump) continue;

            //arrived at the destination
            if(leaves[cur_pos] == leaves.back())
            {
                if(cur_jump < min_jump) min_jump = cur_jump;
                continue;
            }

            //find a leaf to jump on
            for(size_t j = cur_pos + 1; j < leaves.size(); i++)
            {
                //The leaf to jump on should be at a distance of a Fibonacci number
                auto it = find(fib.begin() + 2, fib.end(), leaves[j] - leaves[cur_pos]);
                if(it == fib.end()) continue;

                q.push({j, cur_jump + 1});
            }
        }
    }

    if(min_jump == numeric_limits<int>::max()) return -1;
    return min_jump;
}

 

 

3. 결과

이전 코드와 결과는 같으나, 속도가 많이 상승했다.

하지만 아직 더 개선이 필요하다.