[백준] 9019 DSLR(Java)

문제링크

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

문제분석

• 레지스터에는 0이상 10000미만의 십진수 n을 저장한다.
• 레지스터는 4개의 연산이 존재한다.
  • D : n = 2n % 10000
  • S : (n!=0)이면, n=n-1 / (n==0)이면 n=9999
  • L : n의 각 자리수 왼쪽으로 회전 (d1, d2, d3, d4) -> (d2, d3, d4, d1)
  • R : n의 각 자리수 오른쪽으로 회전 (d1, d2, d3, d4) -> (d4, d1, d2, d3)

입력

• 테스트 케이스 개수 T
• 레지스터의 초기값 A
• 레지스터의 최종값 B
• 0<= A, B <10000

출력

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

풀이

• Register 클래스 선언
  • 현재 저장값인 n
  • 지금까지 수행한 연산을 저장할 operations
  • DSLR메서드 선언

class Register{
    int n;
    String operations; //현재 수행된 연산을 저장할 변수

	//DSLR 연산을 수행하도록 메서드 선언
    public void D(){}
    public void S(){}
    public void L(){}
    public void R(){}
}

• BFS함수
  • visited 배열을 통해 이전에 나온 n값에 중복 계산을 피한다.
  • 현재 n값에 대해 D,S,L,R연산을 수행한 뒤, 중복값이 아니면 큐에 넣는다.

 static String BFS(Register register, int B){
        Queue<Register> q = new LinkedList<>();
        visited[register.getN()] = true; //체크
        q.offer(register);

        //n이 B가 아닐동안 반복
        while(q.peek().getN()!=B){
            Register tmp = q.poll();
            //D, S, L, R연산 수행
            Register[] operation = new Register[4];
            for (int i = 0; i < 4; i++) operation[i] = new Register(tmp.getN(), tmp.getOperations());
            operation[0].D(); operation[1].S(); operation[2].L(); operation[3].R();

            //n값이 이전에 나온 값이 아니면, 큐에 넣는다.
            for (Register op : operation) {
                if(!visited[op.getN()]) {
                    visited[op.getN()] = true;
                    q.offer(op);
                }
            }
        }

        return q.peek().getOperations();
    }

코드

import java.util.*;

class Register{
    int n;
    String operations; //현재 수행된 연산을 저장할 변수

    public Register(int n, String operations) {
        this.n = n;
        this.operations = operations;
    }

    public int getN() {
        return n;
    }

    public String getOperations() {
        return operations;
    }

    public void D(){
        operations+="D";
        n*=2;
        n%=10000;
    }
    public void S(){
        operations+="S";
        if(n==0) n=9999;
        else n-=1;
    }
    public void L(){
        operations+="L";
        int tmp = n/1000;
        n = (n*10)%10000+tmp;
    }
    public void R(){
        operations+="R";
        int tmp = n%10;
        n=n/10 + tmp*1000;
    }
}

public class Main {
    // BFS의 중복 계산을 막기위한 체크배열
    static boolean[] visited = new boolean[10000];;

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        String[] answer = new String[T];

        ArrayList<Integer> A = new ArrayList<>();
        ArrayList<Integer> B = new ArrayList<>();

        for(int i=0; i<T; i++){
            A.add(scanner.nextInt());
            B.add(scanner.nextInt());
        }

        for(int i=0; i<T; i++){
            Arrays.fill(visited, false);//체크배열 초기화
            //각 입력 쌍 A, B에 대해 정답을 찾는다.
            answer[i] = BFS(new Register(A.get(i), ""), B.get(i));
        }

        for (String s : answer) {
            System.out.println(s);
        }
    }
    static String BFS(Register register, int B){
        Queue<Register> q = new LinkedList<>();
        visited[register.getN()] = true; //체크
        q.offer(register);

        //n이 B가 아닐동안 반복
        while(q.peek().getN()!=B){
            Register tmp = q.poll();
            //D, S, L, R연산 수행
            Register[] operation = new Register[4];
            for (int i = 0; i < 4; i++) operation[i] = new Register(tmp.getN(), tmp.getOperations());
            operation[0].D(); operation[1].S(); operation[2].L(); operation[3].R();

            //n값이 이전에 나온 값이 아니면, 큐에 넣는다.
            for (Register op : operation) {
                if(!visited[op.getN()]) {
                    visited[op.getN()] = true;
                    q.offer(op);
                }
            }
        }

        return q.peek().getOperations();
    }
}