BOJ 9019 DSLR

Posted Apr 17, 2024

By Yesung-Lim

10 min read

BOJ 9019 DSLR

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

문제

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 $d_1, d_2, d_3, d_4$라고 하자(즉 $n = ((d_1 × 10 + d_2) × 10 + d_3) × 10 + d_4$라고 하자)

D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 $d_2, d_3, d_4, d_1$이 된다.
R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 $d_4, d_1, d_2, d_3$이 된다.

위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

1234 →$_L$ 2341 →$_L$ 3412 1234 →$_R$ 4123 →$_R$ 3412

따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

입력

프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

출력

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

예제 입력 1

예제 출력 1

LL
L
DDDD

코드

최단거리를 구하는 알고리즘이기 때문에 BFS로 코드를 작성했다.

이번 문제는 고민을 좀 많이 했다.

D,S,L,R 연산을 해 나온 값과 그 값이 나오기까지의 커맨드를 String으로 저장하게 되면 불필요한 값까지 저장되기 때문이었다.

ex)

D
DD
DDS
DDSR
…

과 같이 중복된 값이 계속 저장되게 되기 때문이다.

그렇기 때문에, History 클래스를 만들어 사용했고 아래와 같이 커맨드를 저장했다.

ex)

D(연산 커맨드), -1(부모 노드의 Index (맨 처음일 경우, -1로 설정))
D, 0
S, 4
R, 19
…

그리고 목표 값을 찾았을 때, 역순으로 조회하여 정답을 저장했다.

…
R + …
S + R + …
D + S + R + …
D + D + S + R + …

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

public class Main {

    static class History { // 연산한 커맨드의 기록 클래스
        private char cal;
        private int parentIdx;

        public History(char cal, int parentIdx) {
            this.cal = cal;
            this.parentIdx = parentIdx;
        }
    }

    static StringBuilder sb = new StringBuilder(); // 최종 정답 출력을 위한 StringBuilder

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        char[] commands = {'D', 'S', 'L', 'R'}; // 커맨드 목록
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()), target = Integer.parseInt(st.nextToken()); // 시작 값과 목표 값
            ArrayList<History> history = new ArrayList<>(); // 실행 커맨드를 기억하기 위한 ArrayList
            Queue<Integer> queue = new LinkedList<>(); // BFS를 위한 Queue
            boolean[] visited = new boolean[10000]; // 0 ~ 9999까지의 값 중 이전의 계산으로 인해 한번 발생했던 값을 기억하기 위한 배열
            visited[start] = true; // 시작 값을 발생했던 값이라고 체크
            boolean endCheck = false; // 목표 값을 찾았을 때, 추가적인 연산을 그만두게 하기 위한 플래그

            /** queue와 history의 초기값 설정
             * 초기 값에서 D,S,L,R 각 커맨드에 의해 계산된 값을 queue에 offer하고 실행한 커맨드를 history에 저장
             * 계산된 값들을 visited에 발생한 값으로 설정
             */
            int inits[] = {D(start), S(start), L(start), R(start)};
            for (int j = 0; j < inits.length; j++) {
                history.add(new History(commands[j], -1));
                if(inits[j] == target) {
                    addAnswer(history, history.size() - 1);
                    endCheck = false;
                    break;
                }
                queue.offer(inits[j]);
                visited[inits[j]] = true;
            }

            int idx = 0; // queue에서 offer된 값에 연산된 커맨드의 idx
            while (!queue.isEmpty() && !endCheck) {
                int poll = queue.poll();
                // queue에서 poll한 값에서 D,S,L,R 연산을 한 값들을 check 배열에 저장
                int check[] = {D(poll), S(poll), L(poll), R(poll)};

                for (int j = 0; j < check.length; j++) {
                    if(!visited[check[j]]) { // D,S,L,R 연산을 한 값이 기존에 발생했던 값이 아닐 경우,
                        queue.offer(check[j]); // queue에 D,S,L,R로 연산된 값을 offer하고,
                        visited[check[j]] = true; // 해당 값을 visited 처리
                        history.add(new History(commands[j], idx)); // 해당 커맨드를 History에 저장
                    }

                    if(check[j] == target) { // 만약 연산된 값이 target 값과 동일할 경우,
                        addAnswer(history, history.size() - 1); // History를 이용해 지금까지 실행된 연산 기록을 정답에 추가
                        endCheck = true; // endCheck 플래그 설정
                        break;
                    }
                }
                idx++;
            }
        }

        System.out.println(sb); // 최종 정답 출력
    }

    static int D(int input) {
        return (input << 1) % 10000;
    }

    static int S(int input) {
        return input > 0 ? input - 1 : 9999;
    }

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

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

    static void addAnswer(ArrayList<History> history, int lastIdx) {
        StringBuilder answer = new StringBuilder(); 
        while (lastIdx != -1) { // History 노드의 부모 idx가 -1일 때까지,
            answer.insert(0, history.get(lastIdx).cal); // 커맨드를 읽어 answer 첫 번째 칸에 저장
            lastIdx = history.get(lastIdx).parentIdx; // lastIdx를 조회한 History 노드의 부모 idx로 초기화
        }
        sb.append(answer).append('\n'); // 완성된 answer(커맨드 기록)를 최종 정답 sb에 추가
    }
}

BOJ, BFS

코딩테스트 코테 백준 BOJ BFS 백트래킹 java

This post is licensed under CC BY 4.0 by the author.

문제

입력

출력

예제 입력 1

예제 출력 1

코드

Trending Tags