DSLR

풀이

딱 봐도 너비 우선 탐색으로 풀어야겠다고 생각했습니다. 이 문제의 관건은 DSLR 각 연산을 어떻게 처리하냐 입니다. 처음엔 L연산과 R연산을 할 때 4자리 수가 아닌 숫자들을 처리하기 위해 처음에 4자리 수로 맞추고 시작하면 편할 것 같아서 StringBuilder로 연산을 처리했는데 시간 초과가 떴습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    public static class Calculator {
        public static String calculate(int type, String num) {
            if (num.length() < 4) {
                StringBuilder builder = new StringBuilder();
                builder.append("0".repeat(4 - num.length()));
                builder.append(num);
                num = builder.toString();
            }
            int number = Integer.parseInt(num);
            if (type == 0) {
                number *= 2;
                number %= 10000;
            } else if (type == 1) {
                number--;
                if (number == -1) number = 9999;
            } else if (type == 2) {
                StringBuilder builder = new StringBuilder(num);
                builder.deleteCharAt(0);
                builder.append(num.charAt(0));
                return builder.toString();
            } else if (type == 3) {
                StringBuilder builder = new StringBuilder(num);
                builder.delete(0, 3);
                builder.append(num, 0, 3);
                return builder.toString();
            }
            return String.valueOf(number);
        }
    }

    public static class Temp {
        String number;
        StringBuilder command;
        Temp(String number, StringBuilder command) {
            this.number = number;
            this.command = command;
        }
    }

    public static String bfs(String[] numbers) {
        String number = numbers[0];
        Queue<Temp> queue = new ArrayDeque<>();
        queue.offer(new Temp(number, new StringBuilder()));
        HashSet<String> visited = new HashSet<>();
        visited.add(number);

        while (!queue.isEmpty()) {
            Temp temp = queue.poll();
            if (Integer.parseInt(temp.number) == Integer.parseInt(numbers[1])) return temp.command.toString();
            for(int i = 0; i < 4; i++) {
                if (allContains(temp.number, numbers[1]) && (i == 0 || i == 1)) continue;
                String nextNumber = Calculator.calculate(i, temp.number);
                if (!visited.contains(nextNumber)) {
                    StringBuilder nextCommand = new StringBuilder(temp.command);
                    if (i == 0) nextCommand.append('D');
                    else if (i == 1) nextCommand.append('S');
                    else if (i == 2) nextCommand.append('L');
                    else if (i == 3) nextCommand.append('R');
                    queue.offer(new Temp(nextNumber, nextCommand));
                    visited.add(nextNumber);
                }
            }
        }
        return null;
    }

    public static boolean allContains(String num1, String num2) {
        HashSet<Character> set1 = new HashSet<>();
        HashSet<Character> set2 = new HashSet<>();
        for (char c : num1.toCharArray()) {
            set1.add(c);
        }
        for (char c : num2.toCharArray()) {
            set2.add(c);
        }
        if (set1.equals(set2)) return true;
        return false;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        while (tc-- > 0) {
            String[] numbers = br.readLine().split(" ");
            for (int i = 0; i < 2; i++) {
                if (numbers[i].length() < 4) {
                    StringBuilder builder = new StringBuilder();
                    builder.append("0".repeat(4 - numbers[i].length()));
                    builder.append(numbers[i]);
                    numbers[i] = builder.toString();
                }
            }
            String command = bfs(numbers);
            System.out.println(command);
        }
    }
}

그래서 StringBuilder로 처리하던 것을 정수형으로 처리했습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    public static char[] code = new char[]{'D', 'S', 'L', 'R'};

    public static class Temp {
        int number;
        StringBuilder command;

        Temp(int number, StringBuilder command) {
            this.number = number;
            this.command = command;
        }
    }

    public static String bfs(int num1, int num2) {
        boolean[] visited = new boolean[10000];
        Queue<Temp> queue = new ArrayDeque<>();
        queue.add(new Temp(num1, new StringBuilder()));
        visited[num1] = true;
        while (!queue.isEmpty()) {
            Temp temp = queue.poll();
            if (temp.number == num2) return temp.command.toString();
            for (int i = 0; i < 4; i++) {
                int nextNum = calculate(code[i], temp.number);
                if (!visited[nextNum]) {
                    queue.offer(new Temp(nextNum, new StringBuilder(temp.command).append(code[i])));
                    visited[nextNum] = true;
                }
            }
        }
        return null;
    }

    public static int calculate(char code, int number) {
        if (code == 'D') {
            return number * 2 % 10000;
        } else if (code == 'S') {
            if (number == 0) return 9999;
            else return number - 1;
        } else if (code == 'L') {
            return (number * 10 + number / 1000) % 10000;
        } else if (code == 'R') {
            return number % 10 * 1000 + number / 10;
        }
        return 987654321;
    }

    public static void test() {
        System.out.println(calculate(code[0], 6666));
        System.out.println(calculate(code[1], 9999));
        System.out.println(calculate(code[2], 34));
        System.out.println(calculate(code[3], 21));
    }


    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int tc = scanner.nextInt();
        while (tc-- > 0) {
            int num1 = scanner.nextInt();
            int num2 = scanner.nextInt();
            String result = bfs(num1, num2);
            System.out.println(result);
        }
    }
}

그랬더니 시간초과가 뜨지 않았습니다.

회고