백준 - 숨바꼭질

과정

1. 현재 위치에서 곱하기 연산을 했을 때 target값과 가장 가까운 경우 곱하기 선택
2. 같은 값이 없을 경우 연산(+, -, *)을 했을 때 target 값과 가장 가까운 값을 선택
3. target 값과 같아질 때까지 loop 반복

• 1차 풀이: BFS로 안품..ㅋ
• 가능하면 최대한 많이 곱하게 한다.

from sys import stdin
from collections import deque
n, k = map(int, stdin.readline().split())

cur = n # 수빈이의 현재 위치
cnt = 0 # 움직인 시간

while cur != k:
    tmp1 = cur * 2
    tmp2 = cur + 1
    tmp3 = cur - 1

    tmp = [] # 4, 6, 10
    tmp.append(tmp1)
    tmp.append(tmp2)
    tmp.append(tmp3)

    arr = [] # target에서 뺀 값
    for i in range(3):
        arr.append(abs(k - tmp[i]))

    arr2 = []
    for j in range(3):
        arr2.append(abs(k - tmp[j] * 2))

    min_ = min(arr + arr2)
    if min_ in arr:
        # print(arr.index(min_)) # 최솟값을 저장하고 있는 인덱스 출력
        cur = tmp[arr.index(min_)]
        cnt += 1
    else:
        # print(arr2.index(min_))
        cur = tmp[arr2.index(min_)]
        cnt += 1
    # print(cur)

print(cnt)

• 2차 풀이: BFS로 품. 최종 카운트가 이상함.

from sys import stdin
from collections import deque
n, k = map(int, stdin.readline().split())

def bfs(n, k):
    queue = deque()
    queue.append(n)
    cnt = 0
    tmp = [0]

    while queue:
        cur = queue.popleft()
        print(cur)

        if cur == k:
            return cnt

        queue.append(cur - 1)
        queue.append(cur + 1)
        queue.append(cur * 2)
        cnt += 1
        
print(bfs(n, k))