[백준] 9019번: DSLR - JAVA

🔗 문제 링크

BOJ 9019번: DSLR

9019번: DSLR

 

📝 풀이 과정

숫자와 문자열을 동시에 저장해야 하기 때문에 Register class를 만들어주었다. class에서 D, S, L, R을 한 연산을 처리한 결과를 반환해주기로 하였다.

 

D 연산의 경우 n을 2배한 뒤 값이 9999보다 크다면 %10000 값을 반환하라고 하지만 9999보다 작은 경우에는 %10000을 한다면 원래 값이 반환되므로 num * 2 % 10000을 반환한다.
S 연산의 경우 n == 0일 경우만 9999를 반환하면 되므로, n == 0? 9999 : n - 1을 반환한다.
L 연산의 경우 1000의 자리 숫자를 1의 자리 숫자로 내린 뒤, 나머지 숫자들을 *10한다고 생각하면 쉽다. n % 1000 * 10 + n / 1000
R 연산의 경우 1의 자리 숫자를 1000의 자리 숫자로 올린 뒤, 나머지 숫자들을 / 10하면 결과가 나오게 된다. n % 10 * 1000 + n / 10

 

다음은 일반적인 BFS방식으로 해결할 수 있다. Queue에 초기 Register를 push하고 반복을 돌며 같은 숫자를 반복하지 않도록 하기 위해 visit[10000] 배열을 사용해 방문한 값을 true로 변경한다.

 

💻 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            int A = sc.nextInt(), B = sc.nextInt();
            boolean[] visit = new boolean[10000];
            visit[A] = true;

            Queue<Register> que = new LinkedList<>();
            que.add(new Register(A, ""));

            String ans = "";
            while (!que.isEmpty()) {
                Register cur = que.poll();

                if (cur.num == B) {
                    System.out.println(cur.command);
                    break;
                }

                if (!visit[cur.D()]) {
                    que.add(new Register(cur.D(), cur.command + "D"));
                    visit[cur.D()] = true;
                }
                if (!visit[cur.S()]) {
                    que.add(new Register(cur.S(), cur.command + "S"));
                    visit[cur.S()] = true;
                }
                if (!visit[cur.L()]) {
                    que.add(new Register(cur.L(), cur.command + "L"));
                    visit[cur.L()] = true;
                }
                if (!visit[cur.R()]) {
                    que.add(new Register(cur.R(), cur.command + "R"));
                    visit[cur.R()] = true;
                }

            }
        }

    }

    static class Register {
        int num;
        String command;

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

        int D() {
            return (num * 2) % 10000;
        }

        int S() {
            return num == 0 ? 9999 : num - 1;
        }

        int L() {
            return num % 1000 * 10 + num / 1000;
        }

        int R() {
            return num % 10 * 1000 + num / 10;
        }
    }
}

 

📊 제출 결과