[백준] 1697번 - 숨바꼭질

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

문제

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

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

입력

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

출력

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

힌트

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

---

문제 풀이

# 수빈은 : N, 동생은 : K
# 걸을 때 : X + 1, X - 1
# 순간 이동하는 경우 : 2X로 이동
# 수빈이 동생을 찾을 수 있는 가장 빠른 시간이 몇초 후 인가

from collections import deque
import sys

input = sys.stdin.readline

INF = 1000000
n, k = map(int, input().split())
visited = [False for _ in range(INF)]
arr = [0 for _ in range(INF)]


def bfs(x, k):
    q = deque()
    q.append(x)
    visited[x] = True

    while q:
        a = q.popleft()

        move = [1, -1, a]      # 걷기 : x+1, x-1 / 순간이동 : 2x
        for i in range(3):
            dx = a + move[i]   # 이동한 위치
            if not visited[dx] and 0 <= dx < 100001:  # 방문하지 않고, 범위안에 들어간다면
                arr[dx] = arr[a] + 1    # 앞 위치인 a까지 온 횟수 + 1
                q.append(dx)            # 큐에 dx를 넣고 방문 처리
                visited[dx] = True

            if visited[k]:     # 만약 동생의 위치인 k에 도달하면, arr[k]를 출력시킴
                return arr[k]


print(bfs(n, k))

주의 사항

점 N과 K의 범위가 $0<=N, K<=100,000$이다.
따라서, 100,000을 넘지 않아야 한다고 생각해 INF = 100,001로 지정했지만 계속 런타임 오류가 발생하였다.
만약 `n = 50,002이고 k = 99,999라고 할 때, 50,0002*2 = 100,004이므로 100,001이상으로 저장될 수 있어야 한다.

• 참고 자료