[백준] 9019번 : DSLR - JAVA [자바]

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

bfs 알고리즘 문제이다.

입력 받는 A 에서 부터 연산 DSLR 을 사용해서 만들어진 수들 중 아직 방문하지 않은 수를 큐에 삽입하면서 bfs 알고리즘 탐색을 하다가 숫자 B 가 만들어지면 B를 만든 명령어를 출력하면 된다.

명령어를 저장하는 방법은 visited 와 같은 크기의 String 배열 command 를 만들어서 전의 숫자를 만든 명령어 + 현재 숫자를 만든 명령어 를 저장하였다.

public class bj9019 {

    public static int A, B;
    public static boolean[] visited;
    public static String[] command;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int t = 0; t < T; t++) {
            String line = br.readLine();
            String[] split = line.split(" ");
            A = Integer.parseInt(split[0]);
            B = Integer.parseInt(split[1]);

            visited = new boolean[10001];
            command = new String[10001];
            Arrays.fill(command,"");

            bfs(A, B);
        }
        br.close();
    }

    public static void bfs(int A, int B) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(A);
        visited[A] = true;

        while (!queue.isEmpty()) {
            Integer n = queue.poll();
            if (n == B) {
                System.out.println(command[n]);
                break;
            }
            // D
            int D = (n * 2) % 10000;
            if (!visited[D]) {
                queue.add(D);
                visited[D] = true;
                command[D] = command[n] + "D";
            }
            // S
            int S = n - 1;
            if (n == 0) {
                S = 9999;
            }
            if (!visited[S]) {
                queue.add(S);
                visited[S] = true;
                command[S] = command[n] + "S";
            }
            // L
            int L = n % 1000 * 10 + n / 1000;
            if (!visited[L]) {
                queue.add(L);
                visited[L] = true;
                command[L] = command[n] + "L";
            }
            // R
            int R = n / 10 + n % 10 * 1000;
            if (!visited[R]) {
                queue.add(R);
                visited[R] = true;
                command[R] = command[n] + "R";
            }
        }
    }
}