백준 1697번: 숨바꼭질

백준 1697번: 숨바꼭질

아이디어

BFS(너비 우선 탐색)으로 현재 위치에서 -1, +1 *2 되는 경우를 탐색한다. 배열에 있는 숫자를 1씩 더해서 해당 위치까지 가는데 걸린 시간을 기록한다.

코드

from collections import deque

N, K = map(int, input().split())
pos = [0] * 100001
deq = deque()

def solve(start, end):
    deq.append(start)
    while deq:
        current = deq.popleft()
        if current == end:
            return pos[current]
        plusOne = current + 1
        minusOne = current - 1
        multiplyTwo = current * 2
        if plusOne <= 100000 and pos[plusOne] == 0:
            deq.append(plusOne)
            pos[plusOne] = pos[current] + 1
        if minusOne >= 0 and pos[minusOne] == 0:
            deq.append(minusOne)
            pos[minusOne] = pos[current] + 1
        if 0 < multiplyTwo <= 100000 and pos[multiplyTwo] == 0:
            deq.append(multiplyTwo)
            pos[multiplyTwo] = pos[current] + 1
        

print(solve(N, K))