[백준알고리즘 - 9019] DSLR - java (BFS)

이전 BFS보다는 살짝 까다로운 문제이다.

지나온 루트를 저장해야하기 때문에 pre_num -> 현재 수 이전에 지나친 수를 저장하는 배열,

pre_com -> 현재 수에 도달하기 위해 수행한 명령어를 저장하는 배열을 추가로 선언해주었다.

출력은 Stack의 후입선출방식을 활용하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

class Main{
       public static void main(String[] args) throws IOException {
          BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
          int T=Integer.parseInt(in.readLine());
       
          
          for(int c=0; c<T; c++) {
        	  String input=in.readLine();
        	  int SN=Integer.parseInt(input.split(" ")[0]);
        	  int BN=Integer.parseInt(input.split(" ")[1]);
        	  int[] pre_num=new int[10000];
        	  char[] pre_com=new char[10000];
        	  Queue<Integer> queue=new LinkedList<>();
        	  
                 //초기화
        	  pre_num[SN]=-1;//SN의 이전 숫자는 -1
        	  pre_com[SN]='X';//SN으로 오기 위해 선택한 명령어는 X 
        	  queue.add(SN);
        	  
        	  while(!queue.isEmpty()) {
        		  int now=queue.poll();
        		  if(now==BN) {
        			  Stack<String> stack=new Stack<String>();
        			  char ch;//현재 숫자를 오기 위해 거친 명령어 
        			  while(pre_num[now]!=-1) {
        				  ch=pre_com[now];
        				  stack.add(Character.toString(ch));
        				  now=pre_num[now];
        				
        			  }
        			  
        			  while(!stack.isEmpty())
        			  {
        				  System.out.print(stack.pop());
        			  }
        			  System.out.println();
        			  break;
        		  }
        		  
        		  //D
        		  if(now*2 >9999 && pre_com[(now*2)%10000]=='\0') {
        			  queue.add((now*2)%10000);
        			  pre_num[(now*2)%10000]=now;
        			  pre_com[(now*2)%10000]='D';
        		  }
        		  else if(now*2 < 10000 && pre_com[now*2]=='\0') {
        			  queue.add(now*2);
        			  pre_num[now*2]=now;
        			  pre_com[now*2]='D';
        		  }
        		  
        		  //S
        		  if(now==0 && pre_com[9999]=='\0') {
        			  queue.add(9999);
        			  pre_num[9999]=now;
        			  pre_com[9999]='S';
        		  }
        		  else if(now!=0 && pre_com[now-1]=='\0') {
        			  queue.add(now-1);
        			  pre_num[now-1]=now;
        			  pre_com[now-1]='S';
        		  }
        		  
        		  //L
        		  int ln= (now%10)*10+(now/10%10)*100 +(now/100%10)*1000+(now/1000);
        		  if(pre_com[ln]=='\0') {
        			  queue.add(ln);
        			  pre_num[ln]=now;
        			  pre_com[ln]='L';
        		  }
        		  
        		  //R
        		  int rn=(now%10)*1000+(now/10%10) +(now/100%10)*10+(now/1000)*100;
        		  if(pre_com[rn]=='\0') {
        			  queue.add(rn);
        			  pre_num[rn]=now;
        			  pre_com[rn]='R';
        		  }
        	  
          }
          
                                                                                                                   
          }
        		  
          in.close();
     }