취준/백준
[백준][Python][13913][BFS] 숨바꼭질 4
puff
2020. 3. 8. 15:29
문제 : https://www.acmicpc.net/problem/13913
13913번: 숨바꼭질 4
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는
www.acmicpc.net
2020/02/27 - [취준/백준] - [백준][Python][1697][BFS] 숨바꼭질
BFS 문제다.
링크 걸어놓은 숨바꼭질 문제와 똑같은데, 어떻게 도착했는지를 출력해야 한다.
숨바꼭질 과 푸는 방법이 달라지는데, 차이점은 다음과 같다
- 단순 방문확인으로 썼던 v 딕셔너리를 전 위치를 저장하는데 사용한다.
- 출발위치는 -1 로 하고
- v[현재] = 저번 위치
- 그 후 while문을 돌며 v[도착] ->v[도착 1개전].... 순으로 -1이 나올때까지 history에 저장 후 출력한다.
import sys
from collections import deque
d = dict()
v = dict()
ret = 1000000000000
n,k = [int(i) for i in sys.stdin.readline().rstrip().split()]
history = []
def bfs(n,k):
global ret,d
q = deque()
q.append(n)
d[n] = 0
v[n] = -1
while q:
l = q.popleft()
if l in d:
pass
if l==k:
break
for loc in [l-1,l+1,2*l]:
if loc not in d and 0<=loc <= 100001:
d[loc] = d[l]+1
v[loc] = l
q.append(loc)
bfs(n,k)
print(d[k])
dv = v[k]
history.append(str(k))
while dv != -1:
history.append(str(dv))
dv = v[dv]
print(" ".join(reversed(history)))