BOJ_9019 : DSLR

👉 문제링크

9019번: DSLR

---

---

🔸 문제 분석 🔸

• T번의 테스트 케이스를 돌린다.
  • 계산기는 10진수 4자리 숫자로 0000~9999까지 처리할 수 있다.
  • 4가지 연산 D, S, L, R이 있다.
  • A부터 시작해 B가 되는 최소길이 명령어를 출력한다.
• 가중치가 없는 최단거리(최소경로) 문제이므로 BFS 를 사용한다.
  • 큐에서 현재 숫자와 지금까지의 연산을 기록할 클래스를 만든다.
  • D : 2n%10000
  • S : n-1 (n=1이면, 9999)
  • L : (LShift) n = n*10%10000 + n/1000
  • R : (RShift) n = n/10 + n%10*1000

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static class DSLR {
        String history;
        int num;

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

    private static final int MAX = 10_000;

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

        for (int t = 0; t < T; t++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            boolean[] visited = new boolean[MAX];

            // BFS
            Queue<DSLR> que = new ArrayDeque<>();
            que.offer(new DSLR(A, ""));

            while (!que.isEmpty()) {
                DSLR dslr = que.poll();
                int num = dslr.num;
                String history = dslr.history;

                // B발견하면 종료
                if (num == B) {
                    sb.append(history).append('\n');
                    break;
                }

                if (!visited[num]) {
                    visited[num] = true;

                    // D 연산
                    int temp = (num * 2) % MAX;
                    if (!visited[temp]) {
                        que.offer(new DSLR(temp, history + 'D'));
                    }

                    // S 연산
                    temp = num == 0 ? 9999 : num - 1;
                    if (!visited[temp]) {
                        que.offer(new DSLR(temp, history + 'S'));
                    }

                    // L 연산
                    temp = (num * 10) % 10000 + num / 1000;
                    if (!visited[temp]) {
                        que.offer(new DSLR(temp, history + 'L'));
                    }

                    // R 연산
                    temp = num / 10 + num % 10 * 1000;
                    if (!visited[temp]) {
                        que.offer(new DSLR(temp, history + 'R'));
                    }
                }
            }
        }
        // Output
        System.out.println(sb);
    }
}

🔸 코드 해석 🔸

• 중복 연산을 방지하기 위해 방문체크 용 boolean 배열 visited를 사용한다.
• DSLR 클래스는 현재 숫자 num과 지금 까지의 연산 기록인 history를 갖고있다.
• 큐에서 poll한 뒤 B이면 history를 출력하고 while문을 종료한다.
• B가 아니고, 방문하지 않은 숫자라면 4가지 연산을 수행해 큐에 담는다.

---

🔸 end 🔸

• sift를 큐로 구현해야 한다고 잘못 생각해서 DSLR클래스의 num을 deque로 구현했더니 시간초과가 났다.
• visited를 true로 바꾸는 지점을 que.add하는 곳으로 잘못 생각했다가, que.poll으로 이동시켰다.
• 문제의 분석과 풀이 계획을 적어가며 풀이했다.