13913 숨바꼭질 4

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

#bfs

13913번: 숨바꼭질 4

#코드

#13913 숨바꼭질 4

def f(n,k):
    if n>=k:
        return list(range(n,k-1,-1))
#n이 k보다 크면 -1만 할 수 있기에 1씩 줄어드는 리스트 리턴

    visited=[False]*(2*k+1)
    visited[n]=True

#지금 코드에서 최댓값은 k를 2배한 값이다 인덱스를 고려해서 +1 해주고 리스트 작성 visited 리스트는 탐색 여부를 확#인하는 리스트이다.

    todo=[n]
#큐 작성

    parent={n:n}
#부모 노드, {n:n} 으로 해줌으로써 마지막에 부모노드를 찾을때 마지막 n이 나오도록 해준다.

    while todo:
        nexttodo=[]

#큐 돌리기 다음 큐 리셋

 

        for node in todo:
            if node>=k:
                next=[node-1]
#node가 k보다 크면 -1만 할 수 있음

            elif node>=1 and (k/node)%2==0:
                next=[node*2]
#쉽게 말해 소인수 분해를 했을때 2의 배수가 있어야함 만약 2를 넘었다? 3이나 머다 하면 +1 -1 하는게 더 좋을수도 있#기에 생각 않고 2의 배수만 찾는다 node가 1 이상이 아닐경우 (node = 0 node<k, node = 1 node<k) node가 0이면  #나눌 수가 없다.

            else:
                next=[node-1,node+1,node*2]

#간단하게 표현되지 않는다. 여러가지를 고려해야하는 것은 브루트포스(걍 다 하기)

            for i in next:
                if i<0 or i>2*k:
                    continue
#조건에 맞아야함

                elif i==k:
                    path=[i]
                    parent[i]=node
                    while i!=n:
                        i=parent[i]
                        path.append(i)
                    return path[::-1]
#조건, 답 조건 에도 맞으면 부모 노드를 저장하는 리스트 path를 만든다. 저장 후 반대로 돌려서 n부터 k까지 가는 리스 #트로 리턴

                elif not visited[i]:
                    visited[i]=True
                    parent[i]=node
                    nexttodo.append(i)
#탐색 되지 않았다면 탐색 시키고 todo돌리기

        todo=nexttodo

#todo 리셋

    return None
#못 찾으면 None

n,k=map(int,input().split())
#n,k 입력

order=f(n,k)
#order 저장

if order:
#order가 있다면 None으로 끝나지 않았다면

    print(len(order)-1)
    print(*order)

#시작값을 제외한 길이 = 시간

#order 자체

else:
    print(-1)
#못찾으면 -1 출력

 

#여러가지 코드를 확인하고 최적화의 최적화를 거쳐 148이라는 최단 시간을 달성해버렸다 하하 얻어 갈만한건 bfs를 다른 느낌으로 표현한 것이나 parent 의 사용 visited 가 세련되게 사용된다는 거나 아니면 같은 것이라도 좀더 최적화 시킬 수 있는 방법을 찾는 법( 세세하게 생각해보기) 정도를 얻어간 문제 인것 같다. 사실 숨바꼭질 1 2 3 4 까지 진짜 오래 걸렸는데, 가치 있었던 듯