최소 점프

문제 설명

수직선 상에서 위치하는 home에 도달하기 위해 몇번의 점프를 해야하는지를 확인한다.

점프는 3가지 종류가 있으며 +1, -1, +5가 존재한다.

접근 방법

• BFS를 활용하여 각각의 모든 경우의 수를 queue에 집어넣고, home에 도달하는 순간 답을 출력한다.
• 초기 시작점을 queue에 넣고, +1, -1, +5를 한 경우에 home에 도달하는지 확인한다.
• 만약 도달하지 못한 경우 queue에 집어넣고, 이를 반복하며 점프 횟수를 기록한다.
• 중복되는 경우는 제외하도록 코드를 작성한다.

작성한 코드

from collections import deque
def BFS(home):
    queue = deque()
    queue.append(0)
    answer = 0
    
    while queue:
        for i in range(len(queue)):
            loc = queue.popleft()
            
            for loc_move in [loc+1, loc-1, loc +5]: # 각 경우의 수
                if 0 > loc_move or loc_move > 10000 or loc_move in queue:  # 중복 확인
                    continue
                if loc_move == home: # home에 도달한 경우
                    return answer + 1
                queue.append(loc_move)
        answer += 1
 
def solution(home):
    answer = BFS(home)
    return answer