[백준9019] DSLR -JAVA // le_effort//

bfs로 진행 하고

한 단계에서 D S L R 을 하면서 조건을 충족하면 된다.

 

나는 L연산과 R연산을 할 때 하나하나 배열에다가 각 자리수에 넣어줬는데

ex) 4321

arr[0]=4 

arr[1]=3

arr[2]=2

arr[3]=1;

 

다 풀고 다른 코드를  참고하니까 더 좋은 방법이 있었다

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

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

이런식으로 하면 번거롭게 안해도 되지만 생각이 나지 않아 일일히 구현했다

import java.io.*;
import java.util.*;
public class Main {
    static int t;
    static int arr[];
    static PriorityQueue<Node> q = new PriorityQueue<>();
    static boolean visited[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        t = Integer.parseInt(br.readLine());
        arr = new int[4];
        while(t-- >0) {
            String[] t = br.readLine().split(" ");
            int start = Integer.parseInt(t[0]);    // 시작번호
            int end = Integer.parseInt(t[1]);        // 목표번호
            
            visited = new boolean[10000];    // 4자리수만 됨으로 0~9999
            q.clear();    // 테스트케이스가 여러개니 초기화
            q.add(new Node(start,0,""));
            visited[start] = true;
            while(!q.isEmpty()) {
                Node a = q.poll();
                if(a.num == end) {
                    System.out.println(a.str);
                    break;
                }
                int tmp_num =0;
                for(int i=0; i<4; i++) {
                    switch(i) {
                    case 0:    // D 연산 n을 2배로 바꾸고 9999보다 크면 10000 나누기한 나머지값
                        tmp_num = a.num*2;
                        if(tmp_num>=10000) {
                            tmp_num%=10000;
                        }
                        if(!visited[tmp_num]) {
                            visited[tmp_num] = true;    //우선순위 큐로 했으니 x값 방문이 최소한의 cnt로 가는 것
                            q.add(new Node(tmp_num,a.cnt+1,a.str+"D"));
                        }
                        break;
                    case 1:    // S연산 n에서 1을뺀것 n이 0 이라면 9999가 저장
                        if(a.num==0) {
                            tmp_num = 9999;
                        }
                        else {
                            tmp_num = a.num-1;
                        }
                        if(!visited[tmp_num]) {
                            visited[tmp_num] = true;
                            q.add(new Node(tmp_num,a.cnt+1,a.str+"S"));
                        }
                        break;
                    case 2:    //L연산 n자리수를 왼편으로 회전시키는것 d1 d2 d3 d4 -> d2 d3 d4 d1
                        tmp_num = a.num;
                        for(int j=3; j>=0; j--) {
                            arr[j] = tmp_num%10;
                            tmp_num/=10;
                        }    // 각각의 자리수를 배열에 담아줌
                        tmp_num =0;
                        for(int j=1; j<=3; j++) {
                            tmp_num*=10;
                            tmp_num+=arr[j];
                        }
                        tmp_num*=10;
                        tmp_num+=arr[0];
                        if(!visited[tmp_num]) {
                            visited[tmp_num] = true;
                            q.add(new Node(tmp_num,a.cnt+1,a.str+"L"));
                        }
                        break;
                    case 3:    //R연산  d4 d1 d2 d3
                        tmp_num = a.num;
                        for(int j=3; j>=0; j--) {
                            arr[j] = tmp_num%10;
                            tmp_num/=10;
                        }    // 각각의 자리수를 배열에 담아줌
                        tmp_num = arr[3];
                        for(int j=0; j<=2; j++) {
                            tmp_num*=10;
                            tmp_num+=arr[j];
                        }
                        if(!visited[tmp_num]) {
                            visited[tmp_num] = true;
                            q.add(new Node(tmp_num,a.cnt+1,a.str+"R"));
                        }
                    }
                }
            }
        }
    }
}
class Node implements Comparable<Node>{
    int num,cnt;
    String str;
    Node(int num, int cnt, String str){
        this.num=num;
        this.cnt=cnt;
        this.str = str;
    }
    public int compareTo(Node o) {
        return this.cnt-o.cnt;
    }
}