https://www.acmicpc.net/problem/13913
13913번: 숨바꼭질 4수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일www.acmicpc.net
dp로생각했었는데, 사실 bfs였다.
먼져, -1로 채워진 빈 배열을 만들고, 현재위치를 0으로 초기화시켜준다.
이후 현재위치에서 x+1,x-1,x*2로 확장하며 bfs를 진행한다.
마지막 경로를 알기 위해 배열을 하나 더 만들고, 이 배열에 현재위치의 전위치를 기억시켜준다.
만일 k에 도달했으면, k까지의 시간을 출력하고,
경로를 쭉 따라가면서 시작위치(-1)이 나올때까지 왔던길을 되짚는다.
이후 뒤집고 출력하면 끝!!
재밌는문제였다.
from collections import dequedef bfs(n): que=deque() que.append(n)
arr[n]=0 while que: now=que.popleft()
for next in (now+1,now-1,now*2):
if 0<=next<len(arr) and arr[next]==-1:
arr[next]=arr[now]+1 last_visit[next]=now
if next==k: return
que.append((next)) n,k=map(int,input().split())if n==k:
print(0) print(n) exit()arr=[-1 for _ in range(200001)]
last_visit=arr.copy()bfs(n)print(arr[k])tmp=last_visit[k]answer_list=[k]
while True: answer_list.append(tmp) tmp=last_visit[tmp] if tmp==-1:
answer_list.reverse() breakprint(* answer_list)