DSLR

📍 문제 설명

 

💡 접근

연산의 최소 횟수를 구하면 되는 문제로 BFS를 이용하면 되는 문제였다.

다른 연산으로 덮어씌워지지 않게 해당 숫자 방문처리 하는 배열 사용했다.

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, k;
    static int[][] board,dis;
    static int[] ch,pm, combi, first, last;
    static boolean[] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        first = new int[n];
        last = new int[n];
        for(int i = 0; i < n; i++) {
            int a = kb.nextInt();
            int b = kb.nextInt();
            first[i] = a;
            last[i] = b;
            visited = new boolean[10001];
            //최소 연산횟수 - bfs 사용
            T.solution(first[i], last[i]);
        }

    }


    static void solution(int first, int last) {
        Queue<Register> q = new LinkedList<>();
        //첫 시작 지점 넣기
        q.offer(new Register(first, ""));
        //방문 처리
        visited[first] = true;

        while(!q.isEmpty()) {
            //숫자 빼기
            Register r = q.poll();
            if(r.num == last) {
                System.out.println(r.command);
                break;
            }
            //해당 숫자에서 4가지 연산 수행
            int D = (r.num * 2) % 10000;
            if(!visited[D]) {
                visited[D] = true;
                q.offer(new Register(D, r.command+"D"));
            }
            int S = (r.num == 0) ? 9999 : r.num - 1;
            if(!visited[S]) {
                visited[S] = true;
                q.offer(new Register(S, r.command+"S"));
            }
            int L = r.num % 1000 * 10 + r.num / 1000;
            if(!visited[L]) {
                visited[L] = true;
                q.offer(new Register(L, r.command+"L"));
            }
            int R = r.num % 10 * 1000 + r.num / 10;
            if(!visited[R]) {
                visited[R] = true;
                q.offer(new Register(R, r.command+"R"));
            }
        }
    }

    private static class Register {
        private int num;
        private String command;

        public Register(int num, String command) {
            this.num = num;
            this.command = command;
        }

        @Override
        public String toString() {
            return "Register{" +
                    "num=" + num +
                    ", command='" + command + '\'' +
                    '}';
        }
    }
}