[ 백준 ] 13549 숨바꼭질 3 (python)

 

 

 

 

 

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

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는 정수이다.

 

출력

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

 

예제입력 1

5 17

 

예제출력 1

2

 

🔥 문제 풀이

 

이 문제는 [ 백준 ] 1697 숨바꼭질 (python) 문제에서 변형된 문제로,

현재 위치에서 + 1 or 현재 위치에서 -1만큼 이동할 땐 1초가 소요되지만

현재 위치에서 *2 만큼 이동할 땐 0초가 소요되도록 구현해 줘야한다.

 

문제를 접하고 3가지 경우를 따로따로 다뤄서 queue에 담아주면 되겠다고 생각하고 구현했는데 결과는 틀림😲

 

 

그래서 어디가 문제인지 다시 살펴보니

💡 *2 만큼 이동했을 때 0초가 걸리기 때문에 다음 순서 때 가장 먼저 pop 되어야 한다. ( 우선순위가 가장 높아야 한다 )

따라서 queue의 FIFO 구조를 고려했을 때, *2 만큼 순간이동했을 때는 appendleft()를 사용해서 queue의 제일 앞에 값을 넣어주면 된다.

나머지 다른 두 개의 경우는 평소와 같이 queue의 뒤에 append 시켜주면 됨!

 

 

from collections import deque
 
def bfs(v):
    queue = deque([v])
    arr[v] = 0
 
    while queue:
        now_pos = queue.popleft()
 
        if now_pos == k:
            return arr[now_pos]
 
        if now_pos * 2 < max and arr[now_pos * 2] == -1:
            arr[now_pos * 2] = arr[now_pos]
            queue.appendleft(now_pos * 2)
 
        if now_pos + 1 < max and arr[now_pos + 1] == -1:
            arr[now_pos + 1] = arr[now_pos] + 1
            queue.append(now_pos + 1)
 
        if 0 <= now_pos -1 < max and arr[now_pos - 1] == -1:
            arr[now_pos - 1] = arr[now_pos] + 1
            queue.append(now_pos - 1)
 
n, k = map(int, input().split())
max = 100_001
arr = [-1] * max
 
print(bfs(n))