문제 링크

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

문제 설명

• n에서 k에 도달하기까지 걸리는 최소 시간 출력
• 현재 좌표가 x라고 할 때
  • x+1, x-1로 이동하는데 1초 소요
  • 2*x로 이동하는데 0초 소요

풀이

• 2*x로 이동하는 시간이 0이기 때문에 해당 좌표가 우선적으로 탐색되어야 한다
• 2*x인 좌표를 큐에 appendleft하면 해당 좌표가 우선적으로 탐색하게 된다

느낀 점

• 처음에 재귀적으로, 깊이 우선으로 탐색하거나, DP로 계산하는 방법을 자꾸 생각해보려 했는데 떠오르지 않았다

• 탐색해야 하는 값에 우선순위가 있기 때문에 너비 우선 탐색을 해야 한다

• 이후에도 함수를 만들어 거리가 0인 좌표들을 우선적으로 모두 큐에 넣고, 1인 좌표들을 그 다음 넣고 하는 방식으로 해보려 했는데 인덱스 에러가 났다

  • 거리에 따라 순서대로 넣기 실패

코드

from collections import deque


def bfs():
    dist = [float('inf')] * 200000
    dist[n] = 0
    q = deque([n])
    while q:
        cn = q.popleft()
        if cn == k:
            return dist[cn]
        for i in range(3):
            nn = get_nn(cn, i)
            if not (0 <= nn < len(dist)):
                continue
            if dist[nn] != float('inf'):
                continue
            if i == 0:
                dist[nn] = dist[cn]
                q.appendleft(nn)
            else:
                dist[nn] = dist[cn] + 1
                q.append(nn)


def get_nn(cn, i):
    if i == 0:
        return cn * 2
    if i == 1:
        return cn + 1
    return cn - 1


n, k = map(int, input().split())
print(bfs())