[백준] 9019. DSLR (Java)

 

9019번: DSLR

 

풀이

• BFS로 네 가지 경우 (DSLR)를 전부 탐색한다.
  • int, String을 저장하는 custom class DSLR을 구현했다.
  • 큐에는 (현재 숫자, 지금까지 부른 명령어)를 저장한다.
• 탐색하다가 현재 숫자가 B가 되면 지금까지의 명령어를 출력한다.
• visited[]로 숫자 중복 여부를 확인한다.
• D, S, L, R을 method로 만들어서 사용했다.

 

 

코드

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

public class Main {
    static int T, A, B, ans;
    static Queue<DSLR> q;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());

            bw.write(String.valueOf(solve()));
            bw.newLine();
        }
        br.close();
        bw.close();
    }

    public static String solve() {
        visited = new boolean[10001];
        q = new LinkedList<>();
        q.offer(new DSLR(A, ""));

        while(!q.isEmpty()) {
            int num = q.peek().num;
            String op = q.peek().op;
            q.poll();

            if (num == B) return op;

            int nextNum = D(num);
            if (!visited[nextNum]) {
                visited[nextNum] = true;
                q.offer(new DSLR(nextNum, op + "D"));
            }
            nextNum = S(num);
            if (!visited[nextNum]) {
                visited[nextNum] = true;
                q.offer(new DSLR(nextNum, op + "S"));
            }
            nextNum = L(num);
            if (!visited[nextNum]) {
                visited[nextNum] = true;
                q.offer(new DSLR(nextNum, op + "L"));
            }
            nextNum = R(num);
            if (!visited[nextNum]) {
                visited[nextNum] = true;
                q.offer(new DSLR(nextNum, op + "R"));
            }
        }

        return "";
    }

    public static int D(int num) {
        return (num * 2) % 10000;
    }

    public static int S (int num) {
        return (num + 9999) % 10000;
    }

    public static int L (int num) {
        int temp = num / 1000;
        return (num % 1000) * 10 + temp;
    }
    public static int R (int num) {
        int temp = num % 10;
        return (num / 10) + temp * 1000;
    }

    static class DSLR {
        int num;
        String op;

        public DSLR(int num, String op) {
            this.num = num;
            this.op = op;
        }
    }
}