취준/백준
[백준][Python][13549][BFS] 숨바꼭질 3
puff
2020. 3. 7. 13:27
문제 : 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)