백준 9019번 DSLR JAVA

링크텍스트

설명

L연산은 a%1000*10 + a/1000
R연산은 a%10*1000 + a/10으로 구할 수 있다. BFS 알고리즘을 사용하여 이미 방문한 숫자는 다시 방문하지 않도록 처리하였다.

코드

import java.util.*;
import java.io.*;

class Main {
        static boolean [] check;

	public static void main (String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
	    StringTokenizer st;
	    int t = Integer.parseInt(br.readLine());
	    
	    for(int i=0;i<t;i++){
	        st = new StringTokenizer(br.readLine());
	        
	        int a = Integer.parseInt(st.nextToken());
	        int b = Integer.parseInt(st.nextToken());

            sb.append(bfs(a, b)).append("\n");
	    }
	    
        System.out.print(sb);
	}
	
	public static String bfs(int a, int b){
        Queue<State> q = new LinkedList<>();
        q.add(new State(a, ""));
        check = new boolean[10000];
        check[a] = true;
	    
        while (!q.isEmpty()) {
            State current = q.poll();

            if(current.value==b){
                return current.command;
            }

            int d = D(current.value);
            int s = S(current.value);
            int l = L(current.value);
            int r = R(current.value);

            if(!check[d]){
                check[d] = true;
                q.add(new State(d, current.command+"D"));
            }

            if(!check[s]){
                check[s] = true;
                q.add(new State(s, current.command+"S"));
            }

            if(!check[l]){
                check[l] = true;
                q.add(new State(l, current.command+"L"));
            }

            if(!check[r]){
                check[r] = true;
                q.add(new State(r, current.command+"R"));
            }
        
        }
        
        return "";
	}
	
	public static int D(int a){
	    return (a*2)%10000;
	}

	public static int S(int a){
	    if(a==0){
            return 9999;
        }else
            return a-1;
	}

	public static int L(int a){
	    return a%1000*10 + a/1000;
	}

	public static int R(int a){
	    return a%10*1000 + a/10;
	}
}

class State{
    int value;
    String command;

    State(int value, String command){
        this.value = value;
        this.command = command;
    }
}