1697-숨바꼭질

문제

이 문제에서 수빈이가 움직일 수 있는 경우는 총 3가지로, 1칸앞,1칸뒤, 2배 점프를 사용할 수 있다.

이 경우를 모두 사용하여 해당 위치에 갈 수 있는 가장 최소의 거리를 만들기 위해 BFS알고리즘을 사용하면 바로 쉽게 풀 수 있다.

from collections import deque
def bfs(graph, start):
    dx = [-1,1,2]
    queue = deque()
    queue.append(start)
    while queue:
        x = queue.popleft()
        for i in range(len(dx)):
            if i == 2:
                nx = x*dx[i]
            else:
                nx = x + dx[i]
            if nx<0 or nx>500000:
                continue
            
            if(graph[nx] == 0):
                queue.append((nx))
                graph[nx] = graph[x] + 1
            if(nx == target):
                return
graph = [0]*1000000
start,target = map(int,input().split(' '))
if(start == target):
    print(0)
elif(start > target):
    print(start-target)
else:
    bfs(graph,start)
    print(graph[target])

기존의 널려있는 BFS코드를 조금만 활용할 줄만 알면 쉽게 풀 수 있는 문제이다.