숨바꼭질 4

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

예제 입력 1 

5 17

예제 출력 1 

4

5 10 9 18 17

예제 입력 2 

5 17

예제 출력 2 

4

5 4 8 16 17

 

# 풀이법

x-1, x+1, 2*x 의 경우로 방문하면서 동생을 찾는다.

                    5                                    dist : 0

      4            6              10                  dist : 1

  3  5  8      5 7 9       9 11 20             dist : 2

             . . .             18                       dist : 3

                               17                       dist : 4

 

dist[현재노드]   = 걸린시간 

move[현재노드] = 부모노드

move 배열에 노드들의 기록들이 들어있다.

 

#코드

import sys   
from collections import deque 
 
def bfs():
  global N, K, dist, move
 
  deq = deque()
  deq.append(N)
  cnt = 0
  while deq:
    x = deq.popleft()
    if x == K: 
      print(dist[x])  
      ans = [] 
      # move에 저장된 경로 값을 통해 거슬러올라가면서 ans에 저장 
      while x != N: 
        ans.append(x) 
        x = move[x] 
      ans.append(N)  
      ans.reverse() # 역순으로 저장되어 있으므로 순서를 바꿈 
      print(*ans) 
       
    else: 
      for i in (x+1, x-1, 2*x):
        if 0<=i<=100000 and dist[i]==0:
          deq.append(i)
          dist[i] = dist[x] + 1 
          move[i] = x 
      
if __name__ == "__main__":
  input = sys.stdin.readline
  dist  = [0]*100001
  move  = [0]*100001
  N, K  = map(int, input().split()) 
  bfs()