숨바꼭질 4

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

13913번: 숨바꼭질 4

 

// 코드

import java.util.*;
import java.io.*; 
 
 
public class Main {   
  
  static int N, K;
  // 정답
  static StringBuilder sb = new StringBuilder();
  // dist : 수빈이가 동생을 찾는 가장 빠른시간
  // move : 어떻게 이동해야 하는지에대한 히스토리
  static int[] dist = new int[100001], move = new int[100001];
  
  // 탐색을 하며 찾는다.
  static void bfs() {
    
    Deque<Integer> deq = new ArrayDeque<>();
    deq.offer(N);
    dist[N]  = 1;
    int next = 0;
    
    while(!deq.isEmpty()) {
      int now = deq.poll();
      // 동생을 잡음
      if(now == K) { 
        
        // 최단거리
        sb.append( (dist[now]-1) + "\n");
        
        // 이동 경로를 추적한다.
        Stack<Integer> myStack = new Stack<>();
        myStack.push(now);
        while( now != N ) {
          myStack.push(move[now]);
          now = move[now]; 
        } 
        while( !myStack.isEmpty() ) {
          sb.append(myStack.pop() + " ");
        }
        sb.append("\n");
        return;
      }
      
      // 3개의 탐색방향
      for(int i=0; i<3; ++i) {
        
        // 각각 3개 방향을 설정해준다.
        if(i == 0)      next = now + 1;
        else if(i == 1) next = now - 1;
        else            next = now * 2;
        
        // 필터링..
        if( next < 0 || next > 100000 || dist[next] != 0 ) continue;
        
        // 필터링을 통과하였을 경우
        deq.offer(next);
        dist[next] = dist[now] + 1;
        move[next] = now;
      }
      
    }
    
  }
  
  // main
  public static void main(String[] args) throws Exception{
    
    // Please Enter Your Code Here
    BufferedWriter bw  = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br  = new BufferedReader(new InputStreamReader(System.in)); 
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    N = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());
    
    bfs();
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  } 
}