[백준 9019] DSLR (JAVA)

백준 9019번 문제 - DSLR

9019번: DSLR

---

문제 분석 

 

•  

 

• 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기 존재
  • D: 값을 두 배로 변경 (2n)
    결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다.
  • S: 갑에서 1 뺀 값으로 변경 (n - 1)
    n이 0 이라면 9999 가 대신 레지스터에 저장된다.
  • L: n의 각 자릿수를 왼편으로 회전시키기 ( d1, d2, d3, d4 → d2, d3, d4, d1 )
  • R: n의 각 자릿수를 오른편으로 회전시키기 ( d1, d2, d3, d4 → d4, d1, d2, d3 )
• 계산 전 값(A)과 계산기를 이용해 계산 후 값(B)이 주어졌을 때, A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력

---

해결 포인트

 

• BFS 사용
• while 반복은 queue가 사라지거나, 원하는 숫자가 만들어졌을 때까지
• queue에서 값을 빼고, DSLR 모두 실행시킨 값 큐에 삽입
  • visit 확인으로 이미 만들어진 숫자 또 만들지 않기 ( 메모리 초과 고려 )
• D : 2 * n % 10000
• S : (n + 9999) % 10000 
• L : n * 10 % 10000 + n / 1000
  
  • n * 10 % 10000 → d2, d3, d4를 한자리씩 앞으로
  • + n / 1000 → d1을 맨 뒤로
• R :  n % 10 * 1000 + n / 10
  •  n % 10 * 1000 → d1, d2, d3를 한자맀기 뒤로
  • + n / 10 → d4를 맨 앞으로

 

처음에 DSLR를 계산할 때, L, R을 문자열로 변환하고 회전시켰다. 
이렇게 하니 시간 초과 발생 !

 

---

 

코드

 

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

public class Main {
    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 T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int pre = Integer.parseInt(st.nextToken());
            int result = Integer.parseInt(st.nextToken());

            bw.write(BFS(pre, result) + "\n");
        }

        bw.flush();
        bw.close();
    }

    public static String BFS(int value, int result) {
        Queue<Integer> queue = new LinkedList<>();
        Queue<String> commands = new LinkedList<>();

        boolean [] visit = new boolean[10001];

        String command = "";

        visit[value] = true;
        queue.add(value);
        commands.add(command);

        while (!queue.isEmpty()) {
            value = queue.poll();
            command = commands.poll();

            if (value == result)
                break;

            // D
            int newValue = value * 2 % 10000;
            if(!visit[newValue]) {
                visit[newValue] = true;
                queue.add(newValue);
                commands.add(command + 'D');
            }

            // S
            newValue = (value+9999) % 10000;
            if(!visit[newValue]) {
                visit[newValue] = true;
                queue.add(newValue);
                commands.add(command + 'S');
            }

            // L
            newValue = (value*10)%10000 + (value/1000);
            if(!visit[newValue]) {
                visit[newValue] = true;
                queue.add(newValue);
                commands.add(command + 'L');
            }

            // R
            newValue = (value%10)*1000 + value/10;
            if(!visit[newValue]) {
                visit[newValue] = true;
                queue.add(newValue);
                commands.add(command + 'R');
            }
        }

        return command;
    }
}