문제 출처 : https://www.acmicpc.net/problem/1697
난이도 : 실버 1

---

문제 파악

수빈이는 현재 위치 N에 있고, 동생은 K에 있다.

수빈이는 한 번에 아래 3가지 행동 중 하나를 할 수 있다.

• x -> x - 1
• x -> x + 1
• x -> 2 * x

우리가 구해야 하는 건
N에서 K까지 도달하는 데 걸리는 최소 시간(최소 이동 횟수) 이다.

왜 BFS인가?

이 문제는 “최단 거리” 유형이다.

• 한 번 이동할 때마다 비용이 항상 1
• 가능한 이동(간선)이 x-1, x+1, 2x 로 고정되어 있음
• 어떤 위치에 처음 도달했을 때가 그 위치까지의 최단 시간

즉, 그래프 관점으로 보면

• 정점: 위치(0 ~ 100000)
• 간선: x -> x-1, x -> x+1, x -> 2x
• 최단 거리: BFS로 해결

BFS는 “가까운 것부터” 탐색하니까
K를 처음 만나는 순간의 값이 정답이다.

핵심 아이디어 1) visited 배열은 “방문 여부 + 거리” 역할

여기서 visited[pos]는 단순히 True/False가 아니라

• visited[pos] = start에서 pos까지 걸린 시간(이동 횟수)

로 쓰인다.

그래서

• 아직 방문 안 했으면 0
• 방문하면 visited[next] = visited[now] + 1

이렇게 “거리”를 누적할 수 있다.

---

핵심 아이디어 2) visited 크기를 "최댓값 + 1"로 잡는다

문제에서 위치 범위는 0 ~ 100000 이다.
즉, 배열 인덱스로 쓰려면 길이가 최소 100001이어야 한다.

그래서

• max_pos = 100001
• visited = [0] * max_pos

---

1. 시작점 start를 큐에 넣고 BFS 시작
2. 큐에서 하나 꺼내서(now)
3. 3가지 이동으로 next_pos 만들고
4. 범위 안이고 아직 방문 안 했으면
   • 방문 처리(거리 업데이트)
   • 큐에 넣기
5. now == end가 되는 순간의 visited[now]가 정답

해답 코드

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

# N = 수빈 위치, K = 동생 위치
start, end = map(int, input().split())

def bfs(start, end):
    max_pos = 100001
    visited = [0] * max_pos

    queue = deque()
    queue.append(start)

    while queue:
        now = queue.popleft()

        if now == end:
            return visited[now]

        for next_pos in (now - 1, now + 1, now * 2):
            if 0 <= next_pos < max_pos and visited[next_pos] == 0:
                visited[next_pos] = visited[now] + 1
                queue.append(next_pos)

print(bfs(start, end))

배운 점

x-1, x+1, x*2 를 간선으로 보고 BFS를 써야한다는 사실을 인지는 했지만 막상 적용하는 법이 떠오르지 않았다.
최단 거리 + 간선 비용이 1이면 BFS를 떠올리자
visited 배열을 방문여부 + 거리 저장용으로 쓰는 것을 고려하자.