[Algorithm/Java] 백준 9019번 - DSLR

---

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

---

📌 문제

문제 유형

• 그래프

문제 설명

D, S, L, R 명령을 했을 때 A -> B가 되는 최소 명령을 찾는 문제

1. D는 a을 두 배로
   • 9999보다 크면 10000으로 나눈 나머지 저장
2. S는 a-1을 저장
   • a가 0보다 크면 9999 저장
3. L은 각 자리수 왼쪽으로 회전
   • d2, d3, d4, d1
4. R은 각 자리수 오른쪽으로 회전
   • d4, d1, d2, d3

입력

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

3
1234 3412
1000 1
1 16

출력

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

LL
L
DDDD

🔍 문제 풀이

1. (숫자 상태, 연산 문자열)을 담는 Pair 클래스 생성
2. 시작 숫자를 Pair로 만들어 큐에 넣고 방문 처리
3. 큐에서 하나씩 꺼내며 D, S, L, R 연산 수행
4. 연산 결과가 방문하지 않은 숫자라면 큐에 추가
5. 목표 숫자에 도달하면 해당 Pair의 연산 문자열을 반환

📌 놓친 점

클래스 생성

자바의 큐는 기본적으로 하나의 타입만 저장할 수 있으므로, 숫자 상태와 연산 문자열을 함께 저장하려면 사용자 정의 클래스가 필요하다.

Python의 튜플과 비슷한 개념이다.

BFS를 하면서 두 가지 정보를 같이 저장해야 하기 때문에, num과 ops를 한 번에 저장하는 클래스 Pair를 만든다.

static class Pair {
    int num; // 현재 숫자
    String ops; // 지금까지 연산 문자열

    // 생성자
    public Pair(int num, String ops) {
        this.num = num;
        this.ops = ops;
    }
}

아래와 같이 사용 가능하다.

Pair p = new Pair(1234, "DS");
System.out.println(p.num); // 1234
System.out.println(p.ops); // DS

• 생성자(Constructor) 란?
  • → new Pair(1234, "DS") 처럼 객체를 만들 때 자동으로 값을 저장해주는 역할
  • this.num = num: 왼쪽은 클래스 안의 변수, 오른쪽 num은 매개변수
  • 즉, 값을 클래스 안에 저장해주는 함수

L연산과 R 공식

L과 R 연산은 숫자의 자리수를 회전시키는 연산이다.

예를 들어 1000에 대해 연산을 적용하면 다음과 같은 결과가 나온다.

• 1000 → L → 0001 -> 자바에서는 앞의 0이 생략되어 실제 값은 1
• 1000 → R → 0100 -> 실제 값은 100

자바에서는 정수형 앞에 오는 0을 생략하기 때문에,
연산 결과를 출력할 때 자릿수가 줄어든 것처럼 보일 수 있다.

하지만 연산 자체는 정확히 작동하지만, 결과 출력 시 혼동하지 않도록 하자!

연산	의미
L	숫자를 왼쪽으로 회전 (1234 → 2341)
R	숫자를 오른쪽으로 회전 (1234 → 4123)

L 연산 구현

int l = (n % 1000) * 10 + (n / 1000);

• 뒤 3자리를 왼쪽으로 밀고
• 맨 앞 자리를 맨 뒤에 붙임

R 연산

int r = (n % 10) * 1000 + (n / 10);

• 맨 끝 자리를 맨 앞으로 보내고
• 나머지 3자리는 한 칸 뒤로 밀기

💻 전체 코드

import java.io.*;
import java.util.*;

public class Main {
    static class Pair{
        int num;
        String ops;

        public Pair(int num, String ops){
            this.num = num;
            this.ops = ops;

        }
    }

    public static String bfs(int start, int target) {
        boolean[] visited = new boolean[10_000];

        Deque<Pair> dq = new ArrayDeque<>();
        dq.offer(new Pair(start, ""));
        visited[start] = true;

        while(!dq.isEmpty()){
            Pair cur = dq.poll();

            if(cur.num == target) return cur.ops;

            // D
            int d = (cur.num * 2) % 10_000;
            if(!visited[d]){
                visited[d] = true;
                dq.offer(new Pair(d, cur.ops + "D"));
            }

            // S
            int s = (cur.num == 0) ? 9999 : cur.num - 1;
            if(!visited[s]){
                visited[s] = true;
                dq.offer(new Pair(s, cur.ops + "S"));
            }

            // L
            int l = (cur.num % 1000) * 10 + cur.num / 1000;
            if (!visited[l]) {
                visited[l] = true;
                dq.offer(new Pair(l, cur.ops + "L"));
            }

            // R
            int r = (cur.num % 10) * 1000 + cur.num / 10;
            if (!visited[r]) {
                visited[r] = true;
                dq.offer(new Pair(r, cur.ops + "R"));
            }
        }
        return "";
    }

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

        int t = Integer.parseInt(br.readLine());
        while(t --> 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            System.out.println(bfs(a,b));
        }

    }
}