[Codility] 13.1 FibFrog

FibFrog 문제 풀기

BFS를 이용하여 해결했다.
현재 위치에서 피보나치 수열을 더하면서 다음 위치에 나뭇잎이 있으면 queue에 넣는다. 만약 다음 위치가 도착지라면 반복문을 중단한다.

def solution(A):
    # setting fibonacci numbers
    target = len(A)
    if target == 0:
        return 1

    fibo = [0, 1]
    pre1, pre2 = fibo[-2], fibo[-1]
    while -1 + fibo[-1] <= target:
        fibo.append(pre1 + pre2)
        pre2 = fibo[-1]
        pre1 = fibo[-2]
    #print(fibo)

    ret = -1
    arrival = False
    q = [[-1, 0]]
    visit = [False] * (target + 1)
    while q:
        pos = q[0][0]
        cnt = q[0][1]
        del q[0]
        #print(pos, cnt)
        
        if arrival:
            break

        for f in fibo:
            next_pos = pos + f
            if next_pos == target:
                arrival = True
                ret = cnt + 1
                break
            if next_pos < target and not visit[next_pos] and A[next_pos] == 1:
                q.append([next_pos, cnt + 1])
                visit[next_pos] = True
    
    return ret