9019 : DSLR

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

---

문제

입력

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

출력

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다.

---

접근

• text는 사용한 명령어를 저장하는 배열이다. text[next]에는 text[now].concat("명령어")와 같이 추가한다. 
• 각각의 명령어에 대해, 경우를 나누어 진행한다. 
• text 배열의 경우, null 값으로 초기화 되어있기 때문에, Arrays.fill을 이용하여 공백으로 채워준다. 

---

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static String[] text;
    static int[] visit;
 
    public static void BFS(int A, int B) {
        Queue<Integer> q = new LinkedList<Integer>();
        visit[A] = 1;
        q.add(A);
 
        while (!q.isEmpty() && visit[B] == 0) {
            A = q.poll();
 
            // rule D
            int nextA = (A * 2) % 10000;
            if (visit[nextA] == 0) {
                q.add(nextA);
                visit[nextA] = 1;
                text[nextA]=text[A].concat("D");
            }
 
            // rule S
            nextA = (A == 0) ? 9999 : A - 1;
            if (visit[nextA] == 0) {
                q.add(nextA);
                visit[nextA] = 1;
                text[nextA]=text[A].concat("S");
            }
 
            // rule L
            nextA = (A / 1000) + (10 * (A % 1000));
            if (visit[nextA] == 0) {
                q.add(nextA);
                visit[nextA] = 1;
                text[nextA]=text[A].concat("L");
 
            }
 
            // rule R
            nextA = (1000 * (A % 10)) + (A / 10);
            if (visit[nextA] == 0) {
                q.add(nextA);
                visit[nextA] = 1;
                text[nextA]=text[A].concat("R");
            }
 
        }
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int count = Integer.parseInt(br.readLine());
 
        String[] ans = new String[count];
 
        for (int i = 0; i < ans.length; i++) {
            text = new String[10000];
            visit = new int[10000];
            Arrays.fill(text, "");
 
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
 
            BFS(a, b);
            ans[i] = text[b];
        }
 
        for (int i = 0; i < ans.length; i++) {
            bw.write(ans[i] + "\n");
        }
 
        bw.flush();
        br.close();
 
    }
 
}