[JAVA] 백준 9019번 : DSLR

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

9019번: DSLR

---

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

public class Main {
    static int start, target;
    static boolean[] visit;
    static String[] command = {"D", "S", "L", "R"};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int TC = Integer.parseInt(br.readLine());
        while (TC-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken());
            target = Integer.parseInt(st.nextToken());
            visit = new boolean[10000];
            sb.append(bfs(start)).append("\n");
        }
        System.out.print(sb);
    }

    private static String bfs(int start) {
        Queue<Register> queue = new LinkedList<>();
        queue.add(new Register(start, ""));
        visit[start] = true;
        while (!queue.isEmpty()) {
            Register now = queue.poll();
            if (now.number == target)
                return now.cmd;
            for (String c : command) {
                int next = calculate(now, c);
                //next에 이르기까지 명령어 최소여야 함
                if(!visit[next]){
                    queue.add(new Register(next, now.cmd + c));
                    visit[next] = true;
                }
            }
        }
        return "Error!";
    }

    private static int calculate(Register now, String c) {
        int number = 0, rest;
        switch (c) {
            case "D":
                number = now.number * 2 % 10000;
                break;
            case "S":
                number = now.number == 0 ? 9999 : now.number - 1;
                break;
            case "L":
                int first = now.number / 1000;
                rest = now.number % 1000;
                number = rest * 10 + first;
                break;
            case "R":
                int last = now.number % 10;
                rest = now.number / 10;
                number = last * 1000 + rest;
                break;
        }
        return number;
    }

    private static class Register{
        int number;
        String cmd;

        Register(int number, String cmd) {
            this.number = number;
            this.cmd = cmd;
        }
    }
}

💡 BFS

풀이

• 현재 값을 D/S/L/R 연산한 결과물을 큐에 저장
  • 이때 값은 객체 단위로 정의하며, 필드는 값(int number), 해당 값에 도달하는데 수행된 일련의 명령어(String cmd)
  • 명령어에 대한 중복 탐색을 피하기 위해, 길이가 10000인 int 배열을 생성해, idx에 해당하는 수를 만들기 위해 필요한 최소 명령어 길이를 기록한다
  • 기존 배열에 기록된 값보다 작을 경우만 갱신 및 queue에 넣음
    • 생각해봤는데 어차피 bfs로 진행하면 cmd길이가 오름차순으로 큐에 들어갈텐데... 불필요한 연산을 제거하는게 나을 것 같다
    • int[] => boolean[] 배열로 변경
• D 연산은 number에 *2한 결과물을 %1000 하여 계산하면 됨
• S 연산은 number - 1 이 0미만인지 판단 -> 9999 / num - 1 저장
• L 연산의 경우, d1이 맨 뒤로 가야 함
  • d1을 구함 : first =  num / 1000
  • d2d3d4를 구함 : rest = num % 1000;
  • 조합 : rest * 10 + first
• R 연산의 경우, d4가 맨 앞으로 와야 함
  • d4 구함 : last = num % 10
  • 나머지 앞 3자리 : rest = num /10
  • 조합 : last * 1000 + rest