백준|1697번|숨바꼭질

문제설명
초기 숫자 N과 목표 지점 K를 입력받고 한 번의 연산마다 (-1, +1, *2) 중 하나를 수행할 때 N을 K로 만들기 위해 최소 몇번의 연산이 필요한지 출력하는 문제입니다.

작동 순서
1. N과 K를 입력받습니다.
2. N을 큐에 집어넣습니다.
3. 큐에 들어있는 숫자를 꺼내서 (-1, +1, *2)의 연산을 모두 수행해본뒤 해당 숫자에 방문한적이 없다면(배열의 값이 초기값인 0인경우) 그 숫자에 지금까지의 연산횟수를 입력하고 큐에 집어넣습니다.
4. 목표값을 찾은 경우 반복문을 종료합니다.
5. 배열의 목표값 번째에 있는 수(해당 수에 도달하기 위한 최소의 연산횟수)를 출력합니다.

소스코드

import sys
from collections import deque
N, K = map(int, sys.stdin.readline().split())
num = [0] * 100001
attempt = 0
Find = False
q = deque()
q.append(N)
while not Find:
    while len(q) > 0:
        locate = q.popleft()
        if locate == K:
            Find = True
            break
        if 0 <= locate-1 < 100001 and num[locate-1] == 0:
            num[locate-1] = num[locate]+1
            q.append(locate-1)
        if 0 <= locate+1 < 100001 and num[locate+1] == 0:
            num[locate+1] = num[locate]+1
            q.append(locate+1)
        if 0 <= locate*2 < 100001 and num[locate*2] == 0:
            num[locate*2] = num[locate]+1
            q.append(locate*2)
print(num[K])

후기
풀면서 어려움이 많았던 문제입니다. 어제 풀었던 문제는 골드이고 이 문제는 실버문제였는데도 오히려 더 어려웠던것 같습니다. BFS이면서 DP같기도해서 풀면서 많이 헤맨것 같습니다. 다음부터는 문제를 풀면서 여러가지 알고리즘을 적용해보려는 시도를 해봐야 할 것 같습니다.