[BOJ] 1697 숨바꼭질

https://www.acmicpc.net/problem/1697

1차원 상의 공간에서 +1, -1, *2 만큼 이동이 가능할 때, 목표로 하는 지점으로 최소로 이동하여 도달하는 방법을 구하는 문제이다. BFS와 queue를 사용하여 문제를 해결하였는데, 세 가지의 경우의 수로 이동하는 더 깔끔한 방법이 있었다.(코드2)

코드 1 (good)

from sys import stdin
from collections import deque
input = stdin.readline

n, k = map(int, input().split())
maxSize = 100001
position = [0] * maxSize
queue = deque([n])

def move(cur, nex):
    if (0 <= nex < maxSize) and \
        (position[nex] == 0 or position[cur] + 1 < position[nex]):
        position[nex] = position[cur] + 1
        queue.append(nex)

def solve():
    while queue:
        cur = queue.popleft()
        if cur == k:
            return position[cur]
        move(cur, cur - 1)
        move(cur, cur + 1)
        move(cur, cur * 2)

print(solve())

코드 2 (better)

...
    while queue:
        i = queue.popleft()
        if i == k:
            return arr[i]
        for j in (i + 1, i - 1, i * 2):
            if 0 <= j < maxSize and (arr[j] == 0 or arr[i] + 1 < arr[j]):
                arr[j] = arr[i] + 1
                queue.append(j)

print(solve(position, n, k))