백준 9019번 DSLR

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class DSLR {
    static int T;
    static int A;
    static int B;
    static int[] Larr = new int[4];
    static int[] Rarr = new int[4];
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        T  = Integer.parseInt(st.nextToken());
        for (int test = 0; test < T; test++) {
            st = new StringTokenizer(br.readLine());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            visited = new boolean[10000];
            bfs();

        }
    }
    public static void bfs(){
        Queue<Register> que = new LinkedList<>();
        que.add(new Register(A,"",new StringBuilder()));
        while (!que.isEmpty()){
            Register rg = que.poll();
            visited[rg.n] = true;
            if(rg.n==B){
                System.out.println(rg.pre);
                break;
            }
            int next = D(rg.n);
            if(!visited[next]){
                que.add(new Register(next,"D",rg.pre));
                visited[next] = true;
            }
            next = S(rg.n);
            if(!visited[next]){
                que.add(new Register(next,"S",rg.pre));
                visited[next] = true;
            }
            next = L(rg.n);
            if(!visited[next]){
                que.add(new Register(next,"L",rg.pre));
                visited[next] = true;
            }
            next = R(rg.n);
            if(!visited[next]){
                que.add(new Register(next,"R",rg.pre));
                visited[next] = true;
            }



        }

    }
    public static int D(int n){
        n *=2;
        if(n>9999) n%=10000;
        return n;
    }
    public static int S(int n){
        if(n==0) n=9999;
        else {
            n-=1;
        }
        return n;
    }
    public static int L(int n){
        for (int i = 0; i < 4; i++) {
            int num = 1000;
            for (int j = 0; j < i; j++) {
                num /= 10;
            }
            if(i==0){
                Larr[3] = n/num;
            }
            else {
                Larr[i - 1] = n / num;
            }

            n %=num;

        }
        n=0;
        int num = 1000;
        for (int i = 0; i < 4; i++) {
            n +=Larr[i]*num;
            num/=10;
        }
        return n;
    }
    public static int R(int n){
        for (int i = 0; i < 4; i++) {
            int num = 1000;
            for (int j = 0; j < i; j++) {
                num /= 10;
            }
            if(i==3){
                Rarr[0] = n/num;
            }
            else {
                Rarr[i + 1] = n / num;
            }
            n %=num;
        }
        n=0;
        int num = 1000;
        for (int i = 0; i < 4; i++) {
            n +=Rarr[i]*num;
            num/=10;
        }
        return n;
    }
}
class Register{
    StringBuilder pre = new StringBuilder();
    String str;
    int n;
    public Register(int n,String str, StringBuilder pre){
        this.n = n;
        this.str = str;
        this.pre.append(pre).append(str);
    }
}

풀이방법

👉우선 각각의 D,S,L,R의 동작은 어렵지 않게 구현할 수 있으므로 생략.
L,R동작에서 각 자리수의 배열에 잘라서 추가하고, 다시 배열을 돌며 숫자로 합치는 로직을 사용하였다.
시간복잡도는 조금더 나오겠지만, 0이들어갈때, 반례가 안나오게 하기위해 사용하였다.

📢이문제의 핵심은 큐에 숫자, 이전문자, 현재문자 이렇게 3가지가 들어가야 한다는 것이다.
큐를 꺼내서 이전 문자 + 현재문자를 해주고, DSLR 동작을 수행한 다음 숫자랑 같이 큐에 넣는다.
이때, 꼭 숫자별 중복체크를 수행해주어야 한다.

후기

보통 델타를 사용한 map을 bfs 탐색하는것이 일반적인데, 4가지 DSLR방식으로 bfs를 탐색하는 것이 새로운 유형이었다.
구현할게 많아서 그렇지, 실수만 하지 않는다면 크게 어렵지 않은 문제인것같다.
근데 푸는데 너무 오래걸렸다..
다른 클래스 노드를 만들어서 넣는 방법에 익숙하지 않아서 그런것 같다.