백준 1697

수빈이와 동생의 위치가 주어지고,
수빈이가 현재 위치 X에 대해 X - 1, X + 1, 2 * X로 이동 가능할 때,
수빈이가 동생의 위치로 가는 가장 빠른 시간을 구하는 문제이다.

처음에는 2 * X를 최대한 활용하고,
X - 1, X + 1로 세부 거리를 조정하는 방법을 떠올렸다.

그런데 수빈이의 초기 위치를 기준으로,
이동 가능한 3가지 경우를 고려했을 때,
트리 구조로 모든 경우를 그려볼 수 있었다.

DFS, BFS 중 BFS를 사용한 이유는 다음과 같다.

1) DFS는 모든 경로에 대해 깊은 곳까지 탐색하므로 최단 시간을 보장할 수 없다.
2) BFS는 시간 노드(위치)부터 탐색을 시작해서 목표 노드에 도달하는 순간이 최단 시간이라 할 수 있다.

그리고 불필요한 탐색을 줄이기 위해 visited 리스트를 활용하여,
이미 방문한 노드(위치)라면 추가로 탐색하지 않았다.

또한, 이동해야 하는 위치(next_pos)가 범위를 벗어나는 경우도 탐색하지 않았다.

위의 과정을 반복하며,
현재 위치가 동생의 위치와 같다면 visited[pos] - 1을 반환했다.

코드(정답)는 다음과 같다.

# 1697

import sys
from collections import deque


def bfs(n, k):
    q = deque()
    visited = [0] * 100001

    q.append(n)
    visited[n] = 1
    while q:
        pos = q.popleft()

        if pos == k:
            return visited[pos] - 1

        for next_pos in [pos - 1, pos + 1, pos * 2]:
            if 0 <= next_pos <= 100000 and visited[next_pos] == 0:
                q.append(next_pos)
                visited[next_pos] = visited[pos] + 1
    
    # 예외 처리
    return -1


n, k = map(int, sys.stdin.readline().split())

ans = bfs(n, k)
print(ans)

참고

https://www.youtube.com/watch?v=O8K5A9ojrVw