백준 : 9019

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

9019번: DSLR

 

BFS 탐색 문제이지만 이동방향이 D S R L 네가지로 주어진다.

문자열을 처리하기위해 뒤로가는것은 앞으로 9999번가고 나머지연산을 하는것과 같닫는것을 이용하면 

소스코드를 많이 줄일수가 있다.

 

package com.ssay.algo;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class B9019 {
    static int T;
    static int A,B;
    static boolean visit[];
    static class Pair{
        int n;
        String sb;
        public Pair(int n, String sb) {
            super();
            this.n = n;
            this.sb = sb;
        }
    }
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        T = Integer.parseInt(br.readLine());
        
        for(int t=1;t<=T;t++) {
            String str[] = br.readLine().split(" ");
            
            A = Integer.parseInt(str[0]);
            B = Integer.parseInt(str[1]);
                    
            visit = new boolean[10000];
            String Answer = null;
            
            
            Queue<Pair> q = new LinkedList<Pair>();
            q.add(new Pair(A, ""));
            visit[A] = true;
            while(!q.isEmpty()) {
                boolean isEscape = false;
                int size = q.size();
                for(int s=0;s<size;s++) {
                    Pair tmp = q.poll();
                    if(B == tmp.n) {
                        isEscape = true;
                        Answer = tmp.sb;
                        break;
                    }
                    
                    char c[] = new char[4];
                    int next;
                    //D
                        next = (tmp.n*2)%10000;
                        if(!visit[next]) {
                            visit[next] = true;
                            q.add(new Pair(next,tmp.sb +"D"));
                        }
                    //S
                        next = (tmp.n + 9999) %10000;
                        if(!visit[next]) {
                            visit[next] = true;
                            q.add(new Pair(next, tmp.sb+"S"));
                        }
                        
                    int nn = tmp.n;
                    for(int j=3;j>=0;j--) {
                        c[j] = (char) (nn %10 +'0');
                        nn = nn /10;
                    }
                    char copy[] = new char[4];
                    //L
                    for(int j=0;j<4;j++) {
                        copy[j] = c[(j+1)%4];
                    }
                    
                    nn = Integer.parseInt(String.valueOf(copy));
                    if(!visit[nn]) {
                        visit[nn] = true;
                        q.add(new Pair(nn,tmp.sb+"L"));
                    }
                    
                    //R
                    for(int j=0;j<4;j++) {
                        copy[j] = c[(j+3)%4];
                    }
                    nn = Integer.parseInt(String.valueOf(copy));
                    if(!visit[nn]) {
                        visit[nn] = true;
                        q.add(new Pair(nn,tmp.sb+"R"));
                    }
                    
                }
                
                if(isEscape) break;
                
            }
            System.out.println(Answer);
            
        }
                
    }
}