백준 13913 숨바꼭질4

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

13913번: 숨바꼭질 4

dp로생각했었는데, 사실 bfs였다.

 

먼져, -1로 채워진 빈 배열을 만들고, 현재위치를 0으로 초기화시켜준다.

이후 현재위치에서 x+1,x-1,x*2로 확장하며 bfs를 진행한다.

마지막 경로를 알기 위해 배열을 하나 더 만들고, 이 배열에 현재위치의 전위치를 기억시켜준다.

만일 k에 도달했으면, k까지의 시간을 출력하고,

경로를 쭉 따라가면서 시작위치(-1)이 나올때까지 왔던길을 되짚는다.

이후 뒤집고 출력하면 끝!!

재밌는문제였다.

 

from collections import deque

def 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()
        break
print(* answer_list)