백준 13549. 숨바꼭질 3

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

from collections import deque


def bfs(n, k):
    q = deque([n])
    arr = [-1] * 100001  # 방문 여부 및 걸린 시간 저장 (-1: 미방문)
    arr[n] = 0  # 시작점은 0초

    while q:
        v = q.popleft()

        if v == k:  # 동생 위치에 도달하면 시간 반환
            return arr[v]

        # 순간이동 (우선적으로 처리, 가중치 0)
        if 0 <= 2 * v < 100001 and arr[2 * v] == -1:
            arr[2 * v] = arr[v]  # 순간이동은 시간 증가 X
            q.appendleft(2 * v)  # 큐의 앞에 추가 (우선 탐색)

        # 걷기 (가중치 1)
        for next_v in (v - 1, v + 1):
            if 0 <= next_v < 100001 and arr[next_v] == -1:
                arr[next_v] = arr[v] + 1  # 1초 증가
                q.append(next_v)  # 큐의 뒤에 추가 (나중 탐색)


n, k = map(int, input().split())  # 수빈 위치, 동생 위치
print(bfs(n, k))

여기서 *2 를 +1, -1보다 뒤에 배치하면 틀린다...

🛑 순간이동을 큐 앞에 넣어야 하는 이유

✅ popleft()는 큐의 앞에서 데이터를 가져오므로, 먼저 넣은 값이 먼저 탐색됨.
✅ 순간이동(*2)은 시간이 0초이므로 가장 빨리 탐색해야 최단 경로가 보장됨.
✅ 만약 순간이동을 큐 뒤에 넣으면, 순간이동이 늦게 처리되어 최적의 경로를 놓칠 수 있음!
✅ 따라서 순간이동을 appendleft()로 큐 앞에 추가해야 올바른 정답이 나옴.

💡 즉, 순간이동을 큐 뒤에 넣으면 "시간초과"가 아니라 "틀린 답"이 나올 수도 있습니다! 🚨