본문 바로가기

취준/백준

[백준][Python][13549][BFS] 숨바꼭질 3

문제 : 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의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는

www.acmicpc.net

BFS 문제다.

 

나중에 발견하고 풀었는데, 기존 1,4와는 다른 문제여서 고생했다.

 

이 문제는, 2*X를 하는 순간이동은 시간이 소요되지 않는다.

따라서, X-1, X+1 이동의 경우는 append 를 통해 큐의 뒤에 추가해야 하고,

2*X의 경우에는 appendleft 를 통해 큐 앞에, 현재 탐색 상태에서 탐색을 해야한다.

또한, 큐에다 (현재위치, 현재 소요시간) 을 넣어주고, 2*X의 경우에는 소요시간 + 1 을 하지 말아야 한다.

(deque 를 사용한다고 가정한다.)

 

from collections import deque

n,k = [int(i) for i in input().split()]
q = deque()
v = [False]*200001

ret = 9123412341
q.append((n,0))

while q :
    cur = q.popleft()
    v[cur[0]] = True
    
    if cur[0] == k:
        if ret >= cur[1]:
            ret= cur[1]
        else:
            break
    
    if cur[1] > ret:
        break

    if cur[0]*2 <=200000 and not v[cur[0]*2] :
        q.appendleft((cur[0]*2, cur[1]))
    if cur[0]-1 >=0 and not v[cur[0]-1] :
        q.append((cur[0]-1,cur[1]+1))
    if cur[0]+1 <=200000 and not v[cur[0]+1] :
        q.append((cur[0]+1,cur[1]+1))


print(ret)