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

1. 코드

from collections import deque

n, k = map(int, input().split())
q = deque([n])
visited = [-1] * 100001
visited[n] = 0

while q:
    v = q.popleft()
    if v == k:
        print(visited[v])
        break

    if 0 <= v-1 < 100001 and visited[v-1] == -1:
        visited[v-1] = visited[v] + 1
        q.append(v-1)

    if 0 <= v+1 < 100001 and visited[v+1] == -1:
        visited[v+1] = visited[v] + 1
        q.append(v+1)

    # visited[v] < visited[v*2]: 방문 좌표에 대해 도착에대한 최단시간 값 최신화를 할 수 있다.
    if 0 < v*2 < 100001 and (visited[v*2] == -1 or visited[v] < visited[v*2]):
        visited[v*2] = visited[v]
        q.appendleft(v*2)

2. 후기

최단시간 접근이라는 문제의 조건을 보고 BFS를 떠올렸어야 한다. 본인은 BFS로 접근해야 한다는 생각을 못하고 고민하다가 알고리즘 분류 항목에서 BFS를 사용한다는 힌트를 보고 풀었다.

if문의 v-1, v+1, v*2 순서에 따라 오답으로 나오는 경우가 존재한다. 이 문제의 경우 처음 도착했을 때(-1)만 visited를 갱신해서 발생하는 문제이므로 더 작은 횟수로 방문하는 경우에도 값을 갱신할수 있도록 해야한다.