[BOJ] 1697. 숨바꼭질

📌 문제 제목

문제 링크: BOJ 1697

---

🗒️ 문제 설명

수빈이는 현재 점 N (0 <= N <= 100,000)에 있고, 동생은 점 K (0 <= K <= 100,000)에 있다.

수빈이는 걷거나 순간이동 할 수 있다.

수빈이의 위치가 X일 때, 1초 후에 X-1 or X+1 or 2*X로 이동할 수 있다.

---

💡 문제 해결 아이디어

• 수빈이의 좌표 N을 큐에 넣는다.
• for 문에 걷기와 순간이동한 결과를 넣는다.
• 큐에 popleft를 할 때 K와 같으면 dist[K]를 출력한다.

---

⌛️ 시간 복잡도

• O(N)

---

✅ 최종 코드

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

N, K = map(int, input().split())

queue = deque([N])
dist = [-1] * 100_001
dist[N] = 0

while queue:
    nx = queue.popleft()
    if nx == K:
        print(dist[nx])
        exit(0)
    for res in [2*nx, nx-1, nx+1]:
        if not (0 <= res < 100_001):
            continue
        if dist[res] == -1:
            queue.append(res)
            dist[res] = dist[nx] + 1