[BOJ 13549] 숨바꼭질 3

문제 링크 : https://www.acmicpc.net/problem/13549

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

제한

시간 제한	메모리 제한
2sec	512MB

힌트

수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.

---

풀이

수빈이가 현재 위치 $N$에서 동생이 있는 위치 $K$까지 이동하는 가장 빠른 시간을 구하는 문제다. 이동 방법은 걷기($X-1$, $X+1$)와 순간이동($2 \times X$) 두 가지인데, 걷기는 $1$초가 소요되지만 순간이동은 $0$초가 소요된다는 점이 이 문제의 가장 큰 특징이다.

가중치가 $0$과 $1$로 서로 다른 상황에서 최단 시간을 찾아야 하므로, 일반적인 BFS 탐색보다는 최단경로 알고리즘이나 0-1 BFS의 개념을 적용하는 것이 적절하다.

제공된 소스 코드에서는 이 문제를 해결하기 위해 “순간이동 우선 탐색” 전략을 사용한다. 큐에서 현재 위치를 꺼냈을 때, 해당 위치에서 순간이동으로 도달 가능한 모든 좌표를 하나의 루프 안에서 먼저 처리하는 방식이다.

1. 큐에서 현재 노드(pos, cnt)를 꺼낸다.
2. 현재 위치 pos에서 시작하여, 범위를 벗어나기 전까지 $2$를 계속 곱하며 이동한다 (i *= 2).
3. 순간이동으로 도달한 각 위치 i가 목적지 $K$라면 현재 시간(cnt)을 즉시 출력하고 종료한다.
4. 목적지가 아니라면, 해당 위치 i에서 걷기로 이동할 수 있는 i-1과 i+1 지점을 확인한다.
5. 아직 방문하지 않은 지점이라면 큐에 추가하되, 걷기 연산이므로 시간은 cnt + 1로 증가시킨다.

이 로직은 순간이동이 $0$초라는 점을 이용하여, 동일한 시간대에 도달할 수 있는 모든 “순간이동 체인”을 한꺼번에 확장한다. 따라서 큐에는 항상 시간이 이른 순서대로 노드가 삽입되어 최단 시간을 보장할 수 있게 된다.

좌표의 범위는 다음과 같다.

\[0 \leq N, K \leq 100\,000\]

최대 범위가 $100\,000$이므로 배열의 크기를 넉넉히 잡아 오버플로우를 방지하고, 방문 체크(visit)를 통해 중복 탐색을 막음으로써 $O(N)$ 수준의 시간 복잡도로 해결이 가능하다.

소스코드

Github Link : Source Code

참고 알고리즘 : BFS 탐색