[ 13549 ] [ 0-1 BFS ] 숨바꼭질 3

문제 설명

---

문제

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

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

입력

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

출력

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

---

풀이 과정

일반적인 BFS 문제하고는 좀 다르다. 왜냐하면 걸을때는 1초 걸리고, 순간이동을 하는 경우에는 0초 걸리기 때문에 최단 시간을 구하기 애매하다. 따라서, 현재 위치에서 가능할때까지 2배만 사용해서 쭉 가보고, 왼쪽, 오른쪽으로 이동하는 방식으로 구현해야 한다.

1. BFS를 진행한다.
   • 덱에는 [현재 위치, 현재 위치까지의 비용] 형식으로 저장한다.
   • 현재 위치가 동생이 있는 위치인지 검사한다.
   • 현재위치 * 2, 현재위치 + 1, 현재위치 - 1 순서로 덱에 넣는다.
     • 이 때, 현재 위치 * 2를 덱의 왼쪽에 삽입한다. => 가장 먼저 현재 위치 * 2를 방문하도록 함.
     • 나머지의 경우는 덱의 오른쪽에 삽입한다.
     • 이런 식으로 구현하면, 예시로 비용이 2라고 할 때, N-1, N-2, N, N+1, N+2 위치에서 순간이동을 하여 갈수 있는 모든 지점을 갈 수 있다.
2. BFS 진행 중에, 동생이 있는 위치에 오게 되면 비용을 출력하고 종료한다.

---

소스 코드

---

from collections import deque
import sys

input = sys.stdin.readline
N, K = map(int, input().rstrip().split())

queue = deque([[N, 0]])
visited = [False] * 100001
visited[N] = True
answer = int(10e9)
while queue:
    next_x, cost = queue.popleft()
    if next_x == K:
        answer = cost
        break

    for step in [next_x * 2, next_x+1, next_x-1]:
        if 0 <= step <= 100000 and not visited[step]:
            if step == next_x * 2:
                queue.appendleft([step, cost])
            else:
                queue.append([step, cost+1])
            visited[step] = True

print(answer)