백준 9019 DSLR JAVA

문제

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

---

입출력

---

예제

---

태그

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

풀이

• bfs를 이용한 풀이

• D,S,L,R 각각 해당 숫자에 따른 반환값을 정하는 메서드를 구현한다.

• 주어진 시작 숫자(A)에서부터 D,S,L,R 명령어를 이용해 9999까지 만들 수 있는 숫자의 명령어를 모두 저장한다.

• 이미 만들어진 숫자(방문 O)는 건너뛰고 명령어를 통해 새롭게 만들어진 숫자만 저장한다.

• ex) A : 1234

• 먼저 visited[1234] = true, answer[1234] = "" 부터 시작한다.
• D -> 2368 : visited[2468] = true, answer[2468] = "" + "D" = "D"
• S -> 1233 : visited[1233] = true, answer[1233] = "" + "S" = "S"
• L -> 2341 : visited[2341] = true, answer[2341] = "" + "L" = "L"
• R -> 4123 : visited[4123] = true, answer[4123] = "" + "R" = "R"

• 여기서 또 가지치기처럼 생성된 숫자들을 queue에 넣은 뒤 반복한다.
• ex) L -> L : 3412 : visited[3412] = true, answer[3412] = answer[2341] + "L" = "LL"

• queue에서 poll()한 숫자가 B일 경우 반복문을 종료하고 answer[B]를 출력한다.

---

코드

정답 코드

/**
 * 9019_DSLR
 *
 * bfs를 이용한 풀이
 * D,S,L,R 각각 해당 숫자에 따른 반환값을 정하는 메서드를 구현한다.
 * 주어진 시작 숫자(A)에서부터 D,S,L,R 명령어를 이용해 9999까지 만들 수 있는 숫자의 명령어를 모두 저장한다.
 * 이미 만들어진 숫자(방문 O)는 건너뛰고 명령어를 통해 새롭게 만들어진 숫자만 저장한다.
 * ex) A : 1234
 * 먼저 visited[1234] = true, answer[1234] = "" 부터 시작한다.
 * 그 후 D -> 2368 : visited[2468] = true, answer[2468] = "" + "D" = "D"
 *      S -> 1233 : visited[1233] = true, answer[1233] = "" + "S" = "S"
 *      L -> 2341 : visited[2341] = true, answer[2341] = "" + "L" = "L"
 *      R -> 4123 : visited[4123] = true, answer[4123] = "" + "R" = "R"
 * 여기서 또 가지치기처럼 생성된 숫자들을 queue에 넣은 뒤 반복한다.
 * ex) L -> L : 3412 : visited[3412] = true, answer[3412] = answer[2341] + "L" = "LL"
 *
 * queue에서 poll()한 숫자가 B일 경우 반복문을 종료하고 answer[B]를 출력한다.
 */

public class P_9019 {
    static int T;

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

        for (int tc = 0; tc < T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            // 방문처리용 배열, true이면 이미 만들어진 숫자
            boolean[] visited = new boolean[10000];
            // 명령어를 저장하는 배열, answer[B]가 답
            String[] answer = new String[10000];
            // null이 아닌 빈칸으로 채운다
            Arrays.fill(answer, "");

            Queue<Register> queue = new LinkedList<>();
            // 초기값 설정
            queue.add(new Register(A, answer[A]));
            visited[A] = true;

            while (!queue.isEmpty()) {
                Register p = queue.poll();

                if (p.n == B) {
                    break;
                }

                // 만들어진 숫자를 true로 하고 명령어를 더해준다.
                if (!visited[p.dCommand()]) {
                    visited[p.dCommand()] = true;
                    answer[p.dCommand()] = answer[p.n] + "D";
                    queue.add(new Register(p.dCommand(), answer[p.dCommand()]));
                }

                if (!visited[p.sCommand()]) {
                    visited[p.sCommand()] = true;
                    answer[p.sCommand()] = answer[p.n] + "S";
                    queue.add(new Register(p.sCommand(), answer[p.sCommand()]));
                }

                if (!visited[p.lCommand()]) {
                    visited[p.lCommand()] = true;
                    answer[p.lCommand()] = answer[p.n] + "L";
                    queue.add(new Register(p.lCommand(), answer[p.lCommand()]));
                }

                if (!visited[p.rCommand()]) {
                    visited[p.rCommand()] = true;
                    answer[p.rCommand()] = answer[p.n] + "R";
                    queue.add(new Register(p.rCommand(), answer[p.rCommand()]));
                }
            }

            System.out.println(answer[B]);
        }
    }

    static class Register {
        int n;
        String command;

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

        public int dCommand() {
            return (2*n) % 10000;
        }

        public int sCommand() {
            if (n==0) {
                return 9999;
            }
            else {
                return n-1;
            }
        }

        public int lCommand() {
            return (n % 1000) * 10 + (n / 1000);
        }

        public int rCommand() {
            return (n % 10) * 1000 + (n / 10);
        }
    }
}