[백준] DSLR - 9019번

문제설명

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

9019번: DSLR

 

 

 

기본아이디어

D, S, L, R 명령어를 가진 계산기로 주어진 A 값을 B로 만드는 최소한의 명령어를 생성하는 문제입니다. 일단 최소한의 명령어를 사용한다는 규칙을 보고 먼저 BFS 탐색을 해야겠다 라고 먼저 생각을 하고 접근했습니다.

 

그러고 나서 D, S, L, R 명령어로 값을 계산해주는 함수를 만들었습니다.

 

구현코드

    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(input.readLine());
        for(int test_case = 1; test_case <= T; test_case++){
            StringTokenizer st = new StringTokenizer(input.readLine());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            bfs();
        }
        System.out.println(output);
    }
    static int A, B;
    static class Calc{
        int num;
        String oper;
 
        public Calc(int n, String op){
            this.num = n;
            this.oper = op;
        }
    }
    static void bfs(){
        Queue<Calc> queue = new LinkedList<>();
        Calc a = new Calc(A, "");
        queue.add(a);
        boolean[] visited = new boolean[10000];
        visited[a.num] = true;
        while(!queue.isEmpty()){
            Calc temp = queue.poll();
            if(temp.num == B){
                output.append(temp.oper + "\n");
                return;
            }
 
            int d = D(temp.num);
            if(!visited[d]){
                visited[d] = true;
                queue.add(new Calc(d, temp.oper + "D"));
            }
            d = S(temp.num);
            if(!visited[d]){
                visited[d] = true;
                queue.add(new Calc(d, temp.oper + "S"));
            }
            d = L(temp.num);
            if(!visited[d]){
                visited[d] = true;
                queue.add(new Calc(d, temp.oper + "L"));
            }
            d = R(temp.num);
            if(!visited[d]){
                visited[d] = true;
                queue.add(new Calc(d, temp.oper + "R"));
            }
        }
    }
 
    static int D(int num){
        return (num*2) % 10000;
    }
    static int S(int num){
        int ans = num - 1;
        if(ans < 0)
            return 9999;
        return ans;
    }
    static int L(int num){
        int ans = (num - (num/1000)*1000) * 10 + (num / 1000);
        return ans;
    }
    static int R(int num){
        int ans = num / 10 + (num % 10) * 1000;
        return ans;
    }
 
 

 

 

정리, 기억할 내용

1. 최소한, 제일 먼저 -> BFS, 다익스트라 생각2. 문제 파악은 꼼꼼히, 개발은 빠르게