[백준] 9019 DSLR - BFS

문제 링크 : https://www.acmicpc.net/problem/9019

🍊해결방법

• 조건에 맞는 명령어를 진행해주자
• L과 R이 까다로운데 수식을 사용하자
• L : (num%1000)*10 + num/1000
• R : (num%10)*1000 + (num/10)
• Queue에 넣고 해당 숫자가 나오면 그 때 명령어 출력
• 중복 방문을 제거하기 위해 visit 배열 사용 -> bfs를 활용하기에 최초방문이 최소 명령어

😀풀이

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

public class Main {


    static class Number{
        int n;
        String d;

        public Number(int n, String d){
            this.n=n;
            this.d=d;
        }
    }


    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // D : 2배인데 9999보다 크면 %1000 저장
        // S : -1 인데 음수가 되면 9999 저장
        // L, R

        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        for(int t=1; t<=T; t++){

            StringTokenizer st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            boolean[] visit = new boolean[10001];

            Queue<Number> q = new LinkedList<>();
            q.add(new Number(s, ""));
            visit[s] = true;

            while(!q.isEmpty()){

                Number n = q.poll();

                int num = n.n;
                String dir = n.d;

                if (num == e){
                    sb.append(dir+"\n");
                    break;
                }


                // D
                int D = (num*2)%10000;

                // S
                int S = num == 0 ? 9999 : num-1;

                // L
                int L = (num%1000)*10 + num/1000;

                // R
                int R = (num%10)*1000 + num/10;


                if (!visit[D]){
                    visit[D] = true;
                    q.add(new Number(D, dir+"D"));
                }

                if (!visit[S]){
                    visit[S] = true;
                    q.add(new Number(S, dir+"S"));
                }

                if (!visit[L]){
                    visit[L] = true;
                    q.add(new Number(L, dir+"L"));
                }

                if (!visit[R]){
                    visit[R] = true;
                    q.add(new Number(R, dir+"R"));
                }

            }
        }


        System.out.println(sb);



    }// end main

}