[🥇5 / 백준 13549 / 파이썬] 숨바꼭질 3

 

13549번: 숨바꼭질 3

 

문제

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

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

입력

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

출력

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

 

예제 입력 5 17

예제 출력 2

 

힌트

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

 

풀이

 

BFS + 우선순위 큐인 다익스트라 문제이다.

그래프의 형태는 아니지만 정점이 10만개 있는 다익스트라라고 생각하면 될 것 같다.

 

visited 라는 방문 체크 배열을 만들어두고, n부터 탐색을 진행한다.

탐색은 3방향으로, n-1, n+1, n*2 이다. 

visited의 인덱스 범위 배열을 넘어가지 않게 조건을 주고, 만약 정점 k에 도달했다면 시간을 출력하고 종료한다.

 

import sys, heapq
input = sys.stdin.readline

n,k = map(int,input().split())
visited = [False]*100001
visited[n] = True
hq = [([0,n])]

while hq:
    t,x = heapq.heappop(hq)
    if x == k:
        print(t)
        break
       
    # 순간이동을 먼저 처리해야 한다.
    # 그래야 1 2 와 같은 입력에 0을 출력할 수 있다.
    dx = x*2
    if dx < len(visited) and not visited[dx]:
        visited[dx] = True
        heapq.heappush(hq,(t,dx))
    
    for i in (x+1,x-1):
        if i >= 0 and i < len(visited) and not visited[i]:
            visited[i] = True
            heapq.heappush(hq,(t+1,i))